题目大意：
一个 R*C的矩阵，每个格子内有两种矿yeyenum和bloggium，并且知道它们在每个格子内的数量是多少。
如图所示，最北边有bloggium的收集站，最西边有 yeyenum 的收集站。 传送带只有一个方向直达收集站才有效，不可转弯。
现在要你在这些格子上面安装向北或者向西的传送带(每个格子自能装一种)。问最多能采到多少矿(yeyenum+bloggium)？
定义状态 dp（I，J）表示 前I行，J列，Y+B矿最大值
因为对于任一矿地添加 传送带，仅当其 连接带对应 边界的 收集站时，才有效，且不可弯曲，
所以，对于当前一点 （I，J），其包含的矿Y，与矿B 仅仅有该行该列决定，而与其他行列无关，所有有状态转移方程：
DP（I，J） = MAX（ DP（I-1，J） + Y（I）， DP（I，J-1） + B（J） ）
其中 Y（I） 表示 第J列 前I行 Y矿总和
B（J） 表示 第I行 前J列 B矿总和
编码时，要注意初始化 DP（1，J），DP（I，1）
举 DP（1，J）来讲， 因为与边界收集站相邻，其可以部分到Y，部分到B，应取两者组合情况下的最优值：
令 0 <= K <= J ， DP（1，J） = MAX（ B（K），sum( J..K+1）） //其中 sum（J。。K+1） 表示 K+1到J的Y矿总和， B（K）表示 1到K，B矿总和
对于DP（I，1）而言是同样的
解题代码：
View Code #include#include #include #define MAX(a,b) (a)>(b)?(a):(b)const int N = 510;int Y[N][N],B[N][N];int dp[N][N], yy[N][N], bb[N][N];int n, m;int main(){ while( scanf("%d%d", &n,&m) != EOF) { if( n+m == 0 ) break; memset( Y, 0, sizeof(Y)); memset( B, 0, sizeof(B)); memset( dp,0, sizeof(dp)); memset( yy, 0, sizeof(yy)); memset( bb, 0, sizeof(bb)); for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) scanf("%d", &Y[i][j] ); for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) scanf("%d", &B[i][j] ); // yy[i][j] 第i行， 前j列的 Y矿和 for(int i = 1; i <= n; i++ ) for(int j = 1; j <= m; j++) yy[i][j] = yy[i][j-1] + Y[i][j]; // bb[i][j] 第i列， 前j行的 B矿和 for(int i = 1; i <= m; i++) for(int j = 1; j <= n; j++) bb[i][j] = bb[i][j-1] + B[j][i]; // 初始化 dp[1][i] int sum[N] = { 0}; // 第一行 前I列，B矿和 for(int i = 1; i <= m; i++) sum[i] = sum[i-1]+B[1][i]; for(int j = 1; j <= m; j++) { // 枚举 运输到Y 的长度 for(int i = j; i >= 0; i-- ) dp[1][j] = MAX( dp[1][j], yy[1][i]+(sum[j]-sum[i]) ); } // 初始化 dp[i][1] sum[0] = 0; for(int i = 1; i <= n; i++) sum[i] = sum[i-1]+Y[i][1]; for(int i = 1; i <= n; i++) { //枚举 运输到B 的长度 for(int j = i; j >= 0; j--) dp[i][1] = MAX( dp[i][1], bb[1][j]+(sum[i]-sum[j]) ); } for(int i = 2; i <= n; i++) for(int j = 2; j <= m; j++) dp[i][j] = MAX( dp[i-1][j]+yy[i][j], dp[i][j-1]+bb[j][i] ); printf("%d\n", dp[n][m] ); } return 0;}