Home > Old Blog Posts > USACO 3.3.4 Home on the Range

USACO 3.3.4 Home on the Range


先来介绍下我所用的比较沙茶的方法
设f[i][j][k]代表以坐标(i,j)为右下角,边长为k的正方形是否存在
则f[i][j][k]=f[i][j-1][k-1]&&f[i-1][j][k-1]&&a[i][j]&&a[i-k][j-k]
其中a[i][j]=true当且仅当坐标格(i,j)为完好的草地
相信大家已经看出,这种方法仍旧存在重叠的子问题
f[i][j][k]=true ==> f[i][j][p]=true 其中1<=p<k
所以状态可改为f[i][j]代表以(i,j)为右下角的最大正方形边长
则 f[i][j] = 0                                     !a[i][j]
min(f[i-1][j],f[i][j-1],f[i-1][j-1])+1 a[i][j]
可用滚动数组将空间复杂度优化到线性级别

/*
ID: dementr1
PROG: range
LANG: C++
*/
#include
#include
using namespace std;
ifstream fin("range.in");
ofstream fout("range.out");
bool now[250][250]={false},prev[250][250]={false},a[250][250]={false};
int counter[250]={},N;
void init()
{
	int i,j;
	char s;
	fin>>N;
	for(i=0;i<N;i++)
		for(j=0;j>s;
			if(s=='0') a[i][j]=false;
			else a[i][j]=true;
		}
}
void work()
{
	int i,j,k;
	for(i=0;i<N;i++)
	{
		memset(now,false,sizeof(now));
		for(j=0;j<N;j++)
		{
			now[j][0]=a[i][j];
			for(k=1;k=0&&j-k>=0&&prev[j][k-1]&&now[j-1][k-1]&&a[i][j]&&a[i-k][j-k])
				{
					now[j][k]=true;
					counter[k]++;
				}
			}
		}
		for(j=0;j<N;j++)
			for(k=0;k<N;k++)
				prev[j][k]=now[j][k];
	}
}
void print()
{
	int i;
	for(i=1;i0) fout<<i+1<<" "<<counter[i]<<endl;
}
int main()
{
	init();
	work();
	print();
	return 0;
}

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: