王道机试指南 例题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;
}

运行结果:

全部评论
题目都是英文的,这家是不是对英文的要求很高?
点赞 回复 分享
发布于 2023-03-25 22:09 山东
这家机试共有几道题?
点赞 回复 分享
发布于 2023-03-25 21:54 湖北

相关推荐

点赞 评论 收藏
分享
小浪_Coding:找硬件测试,也可兼顾软测欧, 简历还可以的 ,注意排版,项目写的有条理一点, 然后个人技能多加点, 润色好简历之后就开始沟通海投了,深圳,东莞这边做硬件相关的公司还不少, 医疗类,仪器类的都可以尝试
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务