本文正體字版由OpenCC轉換

動態規劃。前面的章節中還有一個與這個基本上一樣的題。

• 狀態 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