王道机试指南 例题12.11 Monkey Banana

题目：

题目大意：

算法及思路：

这道题和上道例题12.10一样，采用动态规划即可，只是需要变换下半部分输入位于matrix矩阵中的位置，将其放到矩阵的最右边即可。状态转移方程依旧是：

代码：

#include <iostream>

using namespace std;

int main(){
    int t;
    cin>>t;
    for(int k=0;k<t;k++){
        int n0;
        cin>>n0;
        int m,n;
        m=2*n0,n=n0+1;//调整矩阵大小，矩阵最下面和最右边分别补一行0和一列0，方便处理时不越界
        int matrix[m][n],dp[m][n];
        for(int i=0;i<m;i++)//初始化
            for(int j=0;j<n;j++){
                matrix[i][j]=0;
                dp[i][j]=0;
            }
        for(int i=0;i<n0;i++)//上半部分输入位置不变
            for(int j=0;j<i+1;j++)
                cin>>matrix[i][j];
        for(int i=n0;i<m-1;i++)//调整下半部分输入位置
            for(int j=i-n0+1;j<n-1;j++)
                cin>>matrix[i][j];

        for(int i=m-2;i>=0;i--)
            for(int j=0;j<n-1;j++)
                dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+matrix[i][j];//状态转移方程

        cout<<"case "<<k+1<<": "<<dp[0][0]<<endl;
    }
    return 0;
}

运行结果：