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