lightoj 1036 - A Refining Company （dp）

題意:在一個m x n的地圖裡有金礦和銀礦，當你在某個點（x, y）時， 你可以建造一個隻能向西或者向北挖取礦石的履帶車，金礦石隻能被向北移動的履帶車挖取，銀礦石隻能被向西移動的履帶車挖取，并且履帶車不能交叉。給出你每個地點的金礦和銀礦的數量為你用履帶車挖取的最大礦石數量是多少.（履帶車會一直走到邊界）

思路:

當你位于（x, y）時， 你隻有兩個操作：

1）建立一個向北運輸的履帶車，挖一路上的金礦石。

2）建立一個想西運輸的履帶車，挖一路上的銀礦石。

定義dp[i][j] 從(i, j) 出發可以得到的最大礦石數量

于是有狀态方程:dp[i][j] = max(dp[i-1][j] + a[0][i][j], dp[i][j-1] + a[1][i][j])

a[0][i][j]表示從(i, j)向西出發的履帶車可以挖取的銀礦石數量。

a[1][i][j]表示從(i, j)向北出發的履帶車可以挖取的金礦石數量。

/***********************************************
 * Author: fisty
 * Created Time: 2015-08-19 19:48:34
 * File Name   : 1036.cpp
 *********************************************** */
#include <iostream>
#include <cstring>
#include <deque>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <algorithm>
using namespace std;
#define Debug(x) cout << #x << " " << x <<endl
#define Memset(x, a) memset(x, a, sizeof(x))
const int INF = 0x3f3f3f3f;
typedef long long LL;
typedef pair<int, int> P;
#define FOR(i, a, b) for(int i = a;i < b; i++)
#define lson l, m, k<<1
#define rson m+1, r, k<<1|1
#define MAX_N 550
int G[2][MAX_N][MAX_N];
int a[2][MAX_N][MAX_N];
int t;
int m, n;
int dp[MAX_N][MAX_N];
void init(){
    for(int i = 1;i <= m; i++){
        for(int j = 1;j <= n; j++){
            a[0][i][j] = a[0][i][j-1] + G[0][i][j];
        }
    }
    for(int i = 1;i <= m; i++){
        for(int j = 1;j <= n; j++){
            a[1][i][j] = a[1][i-1][j] + G[1][i][j];
        }
    }
}
int main() {
    //freopen("in.cpp", "r", stdin);
    //cin.tie(0);
    //ios::sync_with_stdio(false);
    scanf("%d", &t);
    int cnt = 1;
    while(t--){
        scanf("%d%d", &m, &n);
        for(int z = 0;z < 2; z++){
            for(int i = 1;i <= m; i++){
                for(int j = 1;j <= n; j++){
                    scanf("%d", &G[z][i][j]);
                }
            }
        }
        init();
        for(int i = 1;i <= m; i++){
            for(int j = 1;j <= n; j++){
                dp[i][j] = max(dp[i][j-1] + a[1][i][j], dp[i-1][j] + a[0][i][j]);
            }
        }
        printf("Case %d: %d\n",cnt++, dp[m][n]);
    }
    return 0;
}