题解 | #Monkey Banana Problem#

原题暂未找到可用oj

Description

You are in the world of mathematics to solve the great "Monkey Banana Problem". It states that, a monkey enters into a diamond shaped two dimensional array and can jump in any of the adjacent cells down from its current position (see figure). While moving from one cell to another, the monkey eats all the bananas kept in that cell. The monkey enters into the array from the upper part and goes out through the lower part. Find the maximum number of bananas the monkey can eat.

Input

Input starts with an integer T (≤ 50), denoting the number of test cases.

Every case starts with an integer N (1 ≤ N ≤ 100). It denotes that, there will be 2*N - 1 rows. The ith (1 ≤ i ≤ N) line of next N lines contains exactly i numbers. Then there will be N - 1 lines. The jth (1 ≤ j < N) line contains N - j integers. Each number is greater than zero and less than 215.

Output

For each case, print the case number and maximum number of bananas eaten by the monkey.

• 整个图形拆分成上下两个三角形：上：i：0~n-1 下：i：n~2*n-2
• 从下往上递推
• 注意下三角递推时：左右边界单独考虑

#include <iostream>
using namespace std;

const int maxn=201;
int matrix[maxn][maxn];
int dp[maxn][maxn];

int main(){
  int t;
  while(scanf("%d",&t)!=EOF){
    int casenum=1;
      while(t--){
        int n;
        scanf("%d",&n);
        
        for(int i=0;i<=n-1;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-i-1;j++){
            scanf("%d",&matrix[i][j]);
            dp[i][j]=matrix[i][j];
          }
        }
        
 
        for(int i=2*n-3;i>=n-1;i--){//自下而上递推下三角
          for(int j=0;j<2*n-i-1;j++){
            if(j==0)dp[i][j]+=dp[i+1][j];//左边界
            else if(j==2*n-i-2)dp[i][j]+=dp[i+1][j-1];//右边界
            else dp[i][j]+=max(dp[i+1][j-1],dp[i+1][j]);
          }
        }
        
        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",casenum++,dp[0][0]);
    }
  }

  return 0;
}