DP(递归实现,并保存子问题的解).
#include<iostream>
using namespace std;
int height[105][105];
int dis[105][105];
int dir[4][2]=
{0,1,0,-1,-1,0,1,0};
int c,r;
int dp(int u,int v)
{
if(dis[u][v]) return dis[u][v];
dis[u][v]=1;
for(int i=0;i<4;i++)
{
int x=u+dir[i][0];
int y=v+dir[i][1];
if(x>=0&&x<r&&y>=0&&y<c&&height[u][v]>height[x][y])
{
if(!dis[x][y]) dp(x,y);
if(dis[u][v]<dis[x][y]+1)
dis[u][v]=dis[x][y]+1;
}
}
return dis[u][v];
}
int main()
{
while(scanf("%d%d",&r,&c)!=EOF)
{
int i,j;
for(i=0;i<r;i++)
for(j=0;j<c;j++)
scanf("%d",&height[i][j]);
memset(dis,0,sizeof(dis));
for(i=0;i<r;i++)
for(j=0;j<c;j++)
dp(i,j);
int ans=0;
for(i=0;i<r;i++)
for(j=0;j<c;j++)
if(ans<dis[i][j])
ans=dis[i][j];
printf("%d\n",ans);
}
return 0;
}posted on 2010-08-11 17:31
wuxu 阅读(136)
评论(0) 编辑 收藏 引用 所属分类:
动态规划