随笔-141  评论-9  文章-3  trackbacks-0

比较简单的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 小阮 阅读(253) 评论(0)  编辑 收藏 引用 所属分类: USACO

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理