| ||||||||||
| 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 | |||||||||
前几天已经想到了状态,但是转移想不通。今天突然想通了。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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator