我要啦免费统计
http://acm.pku.edu.cn/JudgeOnline/problem?id=1088
2009年3月19日 星期四
dp: re[i][j]=max{四个方向所得的最大值 的最大值}



#include
<iostream>
using namespace std;
#define MAX 102
int m[MAX][MAX],re[MAX][MAX];
int d[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int r,c;

int dfs(int i,int j)
{
    
if(re[i][j])return re[i][j];
    
int maxv=0,tmp;
    
for(int k=0;k<4;++k){
       
int x=i+d[k][0];
       
int y=j+d[k][1];
       
       
if(x>-1&&x<r&&y>-1&&y<c){
         
if(m[i][j]>m[x][y]){
           tmp
=dfs(x,y)+1;
           
if(tmp>maxv)maxv=tmp;
          }

       }

    }

    
return maxv;
}


int main()
{
    
int ans=0,tmp;
    scanf(
"%d%d",&r,&c);

    
for(int i=0;i<r;++i)
       
for(int j=0;j<c;++j){
            scanf(
"%d",&m[i][j]);
            re[i][j]
=0;     
       }

    
for(int i=0;i<r;++i)
       
for(int j=0;j<c;++j){
          re[i][j]
=dfs(i,j);
          
if(ans<re[i][j])ans=re[i][j];
       }

    
    printf(
"%d\n",ans+1);
    
   
// system("pause");
    return 0;
}

posted on 2009-03-19 22:09 阅读(1391) 评论(0)  编辑 收藏 引用 所属分类: Dynamic programming

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