P248 Monkey Banana Problem

注意分为上下两个三角。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>

using namespace std;

const int MAXN = 101;

int matrix[2*MAXN][MAXN];
int dp[2*MAXN][MAXN];  //(i,j)到底部的最大距离 

int main(){
    int t, n;
    cin >> t;
    for(int k = 1; k <= t; k++){
        cin >> n;
        for(int i = 0; i < n; i++){
            for(int j = 0; j <= i; j++){
                scanf("%d", &matrix[i][j]);
                dp[i][j] = matrix[i][j];
            }
        }
        for(int i = n; i < 2*n-1; i++){
            for(int j = 0; j <= 2*(n-1)-i; j++){
                scanf("%d", &matrix[i][j]);
                dp[i][j] = matrix[i][j];
            }
        }
        for(int i = 2*(n-1)-1; i >= n-1; i--){
            for(int j = 0; j <= 2*(n-1)-i; j++){
                if(j == 0){                      //最左端 
                    dp[i][j] += dp[i+1][j];
                }else if(j == 2*(n-1)-i){        //最右端 
                    dp[i][j] += dp[i+1][j-1];
                }else{
                    dp[i][j] += max(dp[i+1][j], dp[i+1][j-1]);
                }
            }
        }
        for(int i = n-2; i >= 0; i--){
            for(int j = 0; j <= i; j++){
                dp[i][j] += max(dp[i+1][j], dp[i+1][j+1]);
            }
        }
        printf("Case %d: %d\n", k, dp[0][0]);
    }
    return 0;
}