UVa 1366 DP Martian Mining

网上的题解几乎都是一样的：

d(i, j, 0)表示前i行前j列，第(i, j)个格子向左运输能得到的最大值。

d(i, j, 1)是第(i, j)个格子向上运输能得到的最大值。

但是有一个很关键的问题没有解释：

某个格子中的A矿或者B矿一定有其中一种能够运出来吗？有没有可能这个格子没有修建管道，仅仅是为了给其他管道让路，使得总体取得最大值呢？

从题解的状态转移方程上来看，不会的。

自己YY了好久，也没有想到一个能严格证明的方法。。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int maxn =  + ;

 int A[maxn][maxn], B[maxn][maxn];

 int d[maxn][maxn][];

 int main()

 {

     int n, m;

     while(scanf("%d%d", &n, &m) && n)

     {

         for(int i = ; i <= n; i++)

             for(int j = ; j <= m; j++) scanf("%d", &A[i][j]);

         for(int i = ; i <= n; i++)

             for(int j = ; j <= m; j++) scanf("%d", &B[i][j]);

         for(int i = ; i <= n; i++)

             for(int j = ; j <= m; j++) A[i][j] += A[i][j-], B[i][j] += B[i-][j];

         for(int i = ; i <= n; i++)

             for(int j = ; j <= m; j++)

             {

                 d[i][j][] = max(d[i-][j][], d[i-][j][]) + A[i][j];

                 d[i][j][] = max(d[i][j-][], d[i][j-][]) + B[i][j];

             }

         printf("%d\n", max(d[n][m][], d[n][m][]));

     }

     return ;

 }

代码君