UVA - 1366 Martian Mining 三維dp

UVA - 1366 Martian Mining 三維dp

題目大意：在一個n * m的格子上有兩種礦物。A礦只能從右往左運輸，B礦只能從下往上運輸，現在要求你在這格子上鋪設管道（管道不能中斷或者拐彎），用管道來運輸A礦和B礦，使得運輸的A礦和B礦的和最大

解題思路：設dp[i][j][0]為以（i，j）為矩陣的右下角，鋪設從右往左的管道所能運輸的最大值，那麼第i行的第1列到第j列只能鋪設從右往左的管道,所以dp[i][j][0] = max(dp[i-1][j][0],dp[i-1][j][1]) + A[i][j]

設dp[i][j][1]為以(i,j)為矩陣的右下角，鋪設從下往上的管道所能運輸的最大值，那麼第j列的第1行到第i行只能鋪設從下往上的管道，所以dp[i][j][1] = max(dp[i][j-1][0],dp[i][j-1][1]) + B[i][j]

#include
#include
#include
using namespace std;
#define maxn 510
int A[maxn][maxn], B[maxn][maxn], dp[maxn][maxn][2];

int main() {
    int n, m;
    while(scanf(%d%d, &n, &m) != EOF && n + m) {
        for(int i = 1; i <= n; i++) {
            A[i][0] = 0;
            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]);
                if(i != 1)
                    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][0] = max(dp[i-1][j][0], dp[i-1][j][1]) + A[i][j];
                dp[i][j][1] = max(dp[i][j-1][1], dp[i][j-1][0]) + B[i][j];
            }
        printf(%d
,max(dp[n][m][0], dp[n][m][1]));
    }
    return 0;
}