http://acm.pku.edu.cn/JudgeOnline/problem?id=10882009年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
爬 閱讀(1449)
評論(0) 編輯 收藏 引用 所屬分類:
Dynamic programming