| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:非常经典的动态规划,用递归下的记忆化搜索来实现。我将整个实现流程和很多容易错的地方都注释起来,希望能够对那些比较困惑的朋友有所帮助。这程序花了我半个小时调试和写注释,题不在多,经典则行。好晚了,好累,睡觉~~In Reply To:非常经典的动态规划,用递归下的记忆化搜索来实现。我将整个实现流程和很多容易错的地方都注释起来,希望能够对那些比较困惑的朋友有所帮助。这程序花了我半个小时调试和写注释,题不在多,经典则行。好晚了,好累,睡觉~~ Posted by:gfedcba at 2009-02-28 03:37:51 #include"stdio.h"
const int x[]={-1,0,1,0},y[]={0,1,0,-1};
int r,c;
int node[101][101];
int ppt[101][101];
int dfs(int i,int j)
{
int k;
if(ppt[i][j]) return ppt[i][j];
for(k=0;k<4;k++)
if(i+x[k]>=1 && i+x[k]<=r && j+y[k]>=1 && j+y[k]<=r)
if( node[i+x[k]][j+y[k]]<node[i][j] )
if( ppt[i][j]< dfs(i+x[k],j+y[k])+1 )
ppt[i][j]=dfs(i+x[k],j+y[k])+1;
return ppt[i][j];
}
int main()
{
int max=0,i,j;
scanf("%d%d",&r,&c);
for(i=1;i<=r;i++)
for(j=1;j<=c;j++)
{
scanf("%d",&node[i][j]);
ppt[i][j]=0;
}
for(i=1;i<=r;i++)
for(j=1;j<=c;j++)
if(max<dfs(i,j))
max=dfs(i,j);
printf("%d",max+1);
return 1 ;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator