記憶化搜索。d[i][j]=max(d[i'][j'])；a[i][j]<a[i'][j']
以下是我的代碼。
#include<stdio.h>
long r,c,ans,a[508][508],d[508][508];
long xd[]=
{-1,0,1,0},yd[]={0,1,0,-1};
long max(long a,long b)
{
return (a>b?a:b);
}
void init()
{
long i,j;
scanf("%ld%ld",&r,&c);
for(i=1;i<=r;i++)
for(j=1;j<=c;j++)
scanf("%ld",&a[i][j]);
for(i=0;i<=r;i++)
for(j=0;j<=c;j++)
d[i][j]=-1;
ans=0;
}
long dp(long x,long y)
{
long k,t1,t2;
if(d[x][y]!=-1) return d[x][y];
d[x][y]=1;
for(k=0;k<4;k++)
{
t1=x+xd[k];
t2=y+yd[k];
if(t1>=1&&t1<=r&&t2>=1&&t2<=c&&a[t1][t2]<a[x][y])
d[x][y]=max(d[x][y],dp(t1,t2)+1);
}
ans=max(ans,d[x][y]);
return d[x][y];
}
int main()
{
long i,j;
init();
for(i=1;i<=r;i++)
for(j=1;j<=c;j++)
dp(i,j);
printf("%ld\n",ans);
// getchar();getchar();
return 0;
}
posted on 2010-01-06 20:26
lee1r 閱讀(308)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：動態規劃