题目链接：http://www.lightoj.com/volume_showproblem.php?problem=1036
题目大意：如题目图上所示，图上每一个方格可以去上面或者左边， 有两个n*m的矩阵， 第一个是去左边时可获得的价值， 第二个是去上边可获得的价值。求最大价值
题目思路：建立dp数组， 设dp[i][j]是i*j矩阵中可获得的价值， 那么dp[i][j]=max(dp[i-1][j] + a[i][j], dp[i][j-1] + b[i][j])， 其中a数组是向左的前缀和， b数组是向上的前缀和。
代码如下：
#include<bits/stdc++.h> using namespace std; int a[505][505], b[505][505]; int dp[505][505]; void solve(int cases) { int n, m; scanf("%d%d", &n, &m); memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b)); for(int i=1; i<=n; ++ i) { for(int j=1; j<=m; ++ j) { scanf("%d", &a[i][j]); a[i][j] += a[i][j-1]; } } for(int i=1; i<=n; ++ i) { for(int j=1; j<=m; ++ j) { scanf("%d", &b[i][j]); b[i][j] += b[i-1][j]; } } memset(dp, 0, sizeof(dp)); for(int i=1; i<=n; ++ i) { for(int j=1; j<=m; ++ j) { dp[i][j] = max(dp[i-1][j]+a[i][j], dp[i][j-1]+b[i][j]); } } printf("Case %d: %d\n", cases, dp[n][m]); } int main() { int t; scanf("%d", &t); for(int i=1; i<=t; ++ i) solve(i); return 0; }
Light OJ 1036 - A Refining Company(动态规划）
原文：http://www.cnblogs.com/aiterator/p/6441996.html