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 1234556 at 2010-03-14 09:39:19 on Problem 1088
In Reply To:非常经典的动态规划,用递归下的记忆化搜索来实现。我将整个实现流程和很多容易错的地方都注释起来,希望能够对那些比较困惑的朋友有所帮助。这程序花了我半个小时调试和写注释,题不在多,经典则行。好晚了,好累,睡觉~~ Posted by:gfedcba at 2009-02-28 03:37:51
#include <iostream>

using namespace std;

int dx[]={0,-1,0,1};
int dy[]={1,0,-1,0};
int net[124][124];
int cnt[124][124];
int r,c,temp;
int maxnum(int a,int b)
{
    return a>=b?a:b;
}

int dp(int x,int y)
{
    int maxn = 0;
    if (cnt[y][x]>0)
    {
        return cnt[y][x];
    }
    for (int i=0; i<4; i++)
    {
        temp=net[y][x];
        x+=dx[i];
        y+=dy[i];
        if (y>=0&&y<r&&x>=0&&x<c&&temp>net[y][x])
        {
            maxn=maxnum(maxn,dp(x,y));
        }
        x-=dx[i];
        y-=dy[i];
    }
    cnt[y][x]=maxn+1;
    return cnt[y][x];
}

int main()
{
    scanf("%d%d",&r,&c);
    for (int i=0; i<r; i++)
    {
        for (int j=0; j<c; j++)
        {
            scanf("%d",&net[i][j]);
        }
    }
    memset(cnt,0,sizeof(cnt));

    for (int i=0;i<r;i++)
    {
        for (int j=0;j<c;j++)
            dp(j,i);
    }

    for (int i=0;i<r;i++)
    {
        for (int j=0;j<c;j++)
            if (cnt[0][0]<cnt[i][j])
                cnt[0][0]=cnt[i][j];
    }
    printf("%d\n",cnt[0][0]);

    return 0;
}
按照楼主的思路写的代码。 本人菜鸟,刚上路,谢谢楼主的分享!

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