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

前几天已经想到了状态,但是转移想不通。今天突然想通了。

Posted by yygy at 2013-02-04 19:17:57 on Problem 2948
In Reply To:40行代码解决,偶也~发现记忆化搜索比正向递推好用~ Posted by:yzhw at 2010-08-17 18:00:14
> # include <cstdio>
> # include <cstring>
> using namespace std;
> # define N 500
> int n,m;
> int map1[N][N],map2[N][N],dp[N][N];
> int max(int a,int b)
> {
>     return a>b?a:b;
> }
> int solve(int r,int c)
> {
>     if(r<0||c<0) return 0;
>     else if(dp[r][c]!=-1)
>       return dp[r][c];
>     else
>       return dp[r][c]=max(solve(r-1,c)+map1[r][c],solve(r,c-1)+map2[r][c]);
> }
> int main()
> {    
>     while(true)
>     {
>       scanf("%d%d",&n,&m);
>       if(!n&&!m) break;
>       for(int i=0;i<n;i++)
>         for(int j=0;j<m;j++)
>           scanf("%d",&map1[i][j]);
>       for(int i=0;i<n;i++)
>         for(int j=0;j<m;j++)
>           scanf("%d",&map2[i][j]);
>       memset(dp,-1,sizeof(dp));
>       for(int i=0;i<n;i++)
>         for(int j=1;j<m;j++)
>           map1[i][j]+=map1[i][j-1];
>       for(int i=0;i<m;i++)
>         for(int j=1;j<n;j++)
>           map2[j][i]+=map2[j-1][i];
>       printf("%d\n",solve(n,m));
>     }
> }

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