usaco_3_3_4_range_dp求大正方形中包含的小正方形的个数.cpp

usaco自己做的1到5章的代码

/*
ID: wangyuc2
PROB:range
LANG: C++
*/
/*
DP求解大正方形里面包含的小正方形的个数。
从左上角往后扫描，递推公式为：
ss[i][j]=min{c,r,ss[i-1][j-1]+1} i->0..n  j->0..n
其中，c为从当前位置向前算起最长一列有多少相邻的1；
r为从当前位置向前算起最长一行有多少相邻的1；
然后给count中从2~ss[i][j]的数目加上个1；
*/
#include <fstream>
#include <iostream>
#include <string>
#include <memory>
#include <algorithm>
#include <bitset>
#include <queue>
#include <vector>
#define MAXV 255
#define MAXE 1000
#define cin fin
using namespace std;

ifstream fin("range.in");
ofstream fout("range.out");
void swap(int &a,int &b)
{
	int t;
	t=a;
	a=b;
	b=t;
}
int mint(int a,int b,int c=MAXV){
	if(a>b) swap(a,b);
	if(a>c) swap(a,c);
	return a;
}
int main()
{
	int map[MAXV][MAXV];
	int ss[MAXV][MAXV];
	int count[MAXV];
	int i,j,k,m,n,sum;
	char ch;
	cin>>n;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++){
			cin>>ch;
			map[i][j]=ch-'0';
		}
	memset(count,0,sizeof(count));
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
		{
			if(!map[i][j]) {ss[i][j]=0;continue;}
			for(k=i;k>=0;k--) if(map[k][j]==0) break;
			m=i-k;
			for(k=j;k>=0;k--) if(map[i][k]==0) break;
			if(i>0 && j>0)
				m=mint(m,j-k,ss[i-1][j-1]+1);
			else
				m=mint(m,j-k);
			ss[i][j]=m;
			for(k=m;k>=2;k--) count[k]++;
		}

	for(i=2;i<=n;i++)
		if(count[i]) fout<<i<<' '<<count[i]<<endl;
	return 0;
}