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