比较简单的DP。和3.3的Home on the Range差不多. 还简单些。
初始状态
f(i,n) = 1， (i,n)没树；f(i,n)=0，(i,n)有树。
f(n,i) = 1， (i,n)没树；f(i,n)=0，(i,n)有树。
状态转移方程：
i->n-1...1
j->n-1...1
若(i,j)没树
f[i,j] = min3(f[i+1][j], f[i][j+1], f[i+1][j+1])+1
记录最大的f[i,j]即可。
/**//*
ID: lorelei3
TASK: bigbrn
LANG: C++
*/
#include <fstream>
using namespace std;
const int MAXN = 1005;
ifstream fin("bigbrn.in");
ofstream fout("bigbrn.out");
int f[MAXN][MAXN];
inline int min3(int a, int b, int c)
{
int t=a<b?a:b;
return c<t?c:t;
}
int main(){
int i,j,n, t, ans=1;
fin>>n>>t;
for(i=1; i<=n; ++i)
for(j=1; j<=n; ++j)
f[i][j]=-1;
for(i=0; i<t; ++i){
int a,b;
fin>>a>>b;
f[a][b]=0;
}
for(i=1; i<=n; ++i){
if(f[i][n]!=0)
f[i][n]=1;
if(f[n][i]!=0)
f[n][i]=1;
}
for(i=n-1; i>=1; --i)
for(j=n-1; j>=1; --j)
if(f[i][j]!=0){
f[i][j]=min3(f[i+1][j], f[i][j+1], f[i+1][j+1])+1;
if(f[i][j]>ans)
ans=f[i][j];
}
fout<<ans<<endl;
return 0;
}
posted on 2011-02-11 21:56
小阮 阅读(238)
评论(0) 编辑 收藏 引用 所属分类:
USACO