Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

Re:非常经典的动态规划,用递归下的记忆化搜索来实现。我将整个实现流程和很多容易错的地方都注释起来,希望能够对那些比较困惑的朋友有所帮助。这程序花了我半个小时调试和写注释,题不在多,经典则行。好晚了,好累,睡觉~~

Posted by hdyxyx at 2010-05-01 17:25:36 on Problem 1088
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator