Beyond the Void
BYVoid
USACO 3.3.4 Home on the Range 家的范围

这道题可以动态规划。二维的动态规划。

状态定义:G[i][j]为以(i,j)为左上角顶点的正方形的最大边长。

边界条件:G[i][j]为初始读入的矩阵。

状态转移方程: G[i][j]=min{ G[i+1][j] , G[i][j+1] , G[i+1][j+1] } + 1;

解析: G[i+1][j] , G[i][j+1] , G[i+1][j+1]分别为(i,j)向下、向右、向右下一格的状况。在(n-1,n-1)当且仅当三者都为1的时候,正方形才能扩充。从最右下向上,依次扩充即可。

USER: CmYkRgB CmYkRgB [cmykrgb1] TASK: range LANG: C++

Compiling… Compile: OK

Executing… Test 1: TEST OK [0.000 secs, 3088 KB] Test 2: TEST OK [0.011 secs, 3092 KB] Test 3: TEST OK [0.000 secs, 3092 KB] Test 4: TEST OK [0.000 secs, 3092 KB] Test 5: TEST OK [0.022 secs, 3088 KB] Test 6: TEST OK [0.011 secs, 3092 KB] Test 7: TEST OK [0.022 secs, 3088 KB]

All tests OK.

/*
ID: cmykrgb1
PROG: range
LANG: C++
*/
#include <iostream>
#include <fstream>
#define MAXN 251
using namespace std;
ifstream fi("range.in");
ofstream fo("range.out");
int G[MAXN][MAXN],n;
long ans[MAXN];

void init()
{
	long i,j;
	char c;
	fi >> n;
	for (i=1;i<=n;i++)
	{
		for (j=1;j<=n;j++)
		{
			c=10;
			while (c==10 || c==13) c=fi.get();
			G[i][j]=c-48;
		}
	}
}

long min3(long a,long b,long c)
{
	long k=a;
	if (b<k) k=b;
	if (c<k) k=c;
	return k;
}

void dynamic()
{
	long i,j,k;
	for (i=n-1;i>=1;i--)
	{
		for (j=n-1;j>=1;j--)
		{
			if (G[i][j])
				G[i][j]=min3(G[i+1][j],G[i][j+1],G[i+1][j+1])+1;
			if (G[i][j]>1)
				for (k=2;k<=G[i][j];k++)
					ans[k]++;
		}
	}
}

void print()
{
	long i,j;
	for (i=2;i<=MAXN;i++)
	{
		if (ans[i])
			fo << i << ' ' << ans[i] << endl;
	}
	fi.close();
	fo.close();
}

int main()
{
	init();
	dynamic();
	print();
	return 0;
}

上次修改时间 2017-02-03

相关日志