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
爬 阅读(1424)
评论(0) 编辑 收藏 引用 所属分类:
Dynamic programming