HDU4826 Labyrinth

Input

输入的第一行是一个整数T（T < 200），表示共有T组数据。
每组数据的第一行输入两个正整数m，n（m<=100，n<=100）。接下来的m行，每行n个整数，分别代表相应格子中能得到金币的数量，每个整数都大于等于-100且小于等于100。

 

Output

对于每组数据，首先需要输出单独一行”Case #?:”，其中问号处应填入当前的数据组数，组数从1开始计算。
每组测试数据输出一行，输出一个整数，代表根据最优的打法，你走到右上角时可以获得的最大金币数目。

 

Sample Input

2 3 4 1 -1 1 0 2 -2 4 2 3 5 1 -90 2 2 1 1 1 1

 

Sample Output

Case #1: 18 Case #2: 4

 

 

 

使用两个状态转移的数组进行存储，每个格子取两个数组中的最大值。

#include <iostream>
#include <cstring>
using namespace std;

const int MAX = 105;

int G[MAX][MAX];
int dp1[MAX], dp2[MAX];

int main(){
    //freopen("input.txt", "r", stdin);
    int N;
    cin >> N;
    for(int k=1; k<=N; k++){
        int n, m;
        cin >> n >> m;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                cin >> G[i][j];
            }
        }
        
        //第一列只能往下走 
        for(int i=2; i<=n; i++){
            G[i][1] += G[i-1][1];
        }
        
        for(int j=2; j<=m; j++){
            //往下或往右走
            dp1[0] = -10000;
            for(int i=1; i<=n; i++){
                dp1[i] = max(G[i][j-1], dp1[i-1]) + G[i][j];
            }
            //往上或往右走
            dp2[n+1] = -10000;
            for(int i=n; i>0; i--){
                dp2[i] = max(G[i][j-1], dp2[i+1]) + G[i][j];
            }
            //更新当前列
            for(int i=1; i<=n; i++){
                G[i][j] = max(dp1[i], dp2[i]);
            } 
        }
        cout << "Case #" << k << ":" << endl << G[1][m] << endl;
    } 
}