题目大意：找到一个最长的下降序列。
典型的记忆化搜索。
以下是我的代码：
#include<stdio.h>
const long maxn=107;
char name[maxn];
long r,c,h[maxn][maxn],d[maxn][maxn];
const long xd[]={-1,0,1,0},yd[]={0,1,0,-1};
long max(long a,long b)
{
return (a>b?a:b);
}
long dp(long x,long y)
{
if(d[x][y]!=-1)
return d[x][y];
d[x][y]=1;
for(long k=0;k<4;k++)
{
long xx=x+xd[k],yy=y+yd[k];
if(xx>=1&&xx<=r&&yy>=1&&yy<=c&&h[xx][yy]<h[x][y])
d[x][y]=max(d[x][y],dp(xx,yy)+1);
}
return d[x][y];
}
int main()
{
long test;
scanf("%ld",&test);
while(test--)
{
scanf("%s%ld%ld",name,&r,&c);
for(long i=1;i<=r;i++)
for(long j=1;j<=c;j++)
scanf("%ld",&h[i][j]);
for(long i=0;i<=r+1;i++)
for(long j=0;j<=c+1;j++)
d[i][j]=-1;
long ans=0;
for(long i=1;i<=r;i++)
for(long j=1;j<=c;j++)
ans=max(ans,dp(i,j));
printf("%s: %ld\n",name,ans);
}
return 0;
}
posted on 2010-01-19 22:23
lee1r 阅读(369)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：动态规划