动态规划。前面的章节中还有一个与这个基本上一样的题。

• 状态 o F[i][j] 表示以(i,j)为左上角最大正方形的边长

• 初始条件 o 如果(i,N)没有障碍 F[i][N]=1 否则 F[i][N]=0 o 如果(N,i)没有障碍 F[N][i]=1 否则 F[N][i]=0

• 状态转移方程 o F[i][j]=min(F[i+1][j],F[i][j+1],F[i+1][j+1])+1;

  USER: CmYkRgB123 CmYkRgB123 [cmykrgb1]
    TASK: bigbrn
    LANG: C++
  
    Compiling...
    Compile: OK
  
    Executing...
       Test 1: TEST OK [0.011 secs, 6752 KB]
       Test 2: TEST OK [0.000 secs, 6752 KB]
       Test 3: TEST OK [0.000 secs, 6756 KB]
       Test 4: TEST OK [0.000 secs, 6756 KB]
       Test 5: TEST OK [0.000 secs, 6756 KB]
       Test 6: TEST OK [0.000 secs, 6752 KB]
       Test 7: TEST OK [0.000 secs, 6752 KB]
       Test 8: TEST OK [0.011 secs, 6756 KB]
       Test 9: TEST OK [0.011 secs, 6756 KB]
       Test 10: TEST OK [0.032 secs, 6752 KB]
       Test 11: TEST OK [0.032 secs, 6752 KB]
       Test 12: TEST OK [0.032 secs, 6756 KB]
       Test 13: TEST OK [0.022 secs, 6756 KB]
       Test 14: TEST OK [0.022 secs, 6752 KB]
       Test 15: TEST OK [0.043 secs, 6752 KB]
  
    All tests OK.
    
    Your program ('bigbrn') produced all correct answers!  This is your
    submission #3 for this problem.  Congratulations!
    
    

/*
ID: cmykrgb1
PROG: bigbrn
LANG: C++
*/

#include <iostream>
#include <fstream>
#define MAXN 1001

using namespace std;

ifstream fi("bigbrn.in");
ofstream fo("bigbrn.out");

int M[MAXN][MAXN],N,ans;

void init()
{
	int T,x,y,i;
	fi >> N >> T;
	for (i=1;i<=T;i++)
	{
		fi >> x >> y;
		M[x][y]=-1;
	}
}

inline int min(int a,int b,int c)
{
	if (a<=b && a<=c) return a;
	if (b<=a && b<=c) return b;
	return c;
}

void dynamic()
{
	int i,j;
	for (i=1;i<=N;i++)
	{
		if (M[N][i]==0)	M[N][i]=1;
		else			M[N][i]=0;
		if (M[i][N]==0)	M[i][N]=1;
		else			M[i][N]=0;
	}
	for (i=N-1;i>=1;i--)
		for (j=N-1;j>=1;j--)
			if (M[i][j]==-1)
				M[i][j]=0;
			else
			{
				M[i][j]=min(M[i+1][j],M[i][j+1],M[i+1][j+1])+1;
				if (M[i][j]>ans)
					ans=M[i][j];
			}
}

void print()
{
	fo << ans << endl;
	fi.close();
	fo.close();
}

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

上次修改时间 2017-05-22