问题标题: 酷町堂:4952 亢奋的牛牪犇

0
0
程天棋
程天棋
资深守护
资深守护

题目链接: 酷町堂:4952

90分代码

求大佬找错

#include<bits/stdc++.h>
using namespace std;
long long n,m,a[205][205],f[205][205],mx=-0x3f3f3f3f,b,b1;//b是记录m/2+1++的值(左边界),a是记录m/2+1--的值(右边界)
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        } 
    }
    b=b1=m/2+1;
    f[n][m/2+1]=a[n][m/2+1];
    for(int i=n+1;i>=1;i--){
        for(int j=b;j<=b1;j++){
            if(j==b){
                f[i][j]=f[i+1][j+1]+a[i][j];
            }
            else if(j==b1){
                f[i][j]=f[i+1][j-1]+a[i][j];
            }
            else{
                f[i][j]=max(f[i+1][j-1],max(f[i+1][j+1],f[i+1][j]))+a[i][j];
            }
        }
        for(int j=1;j<=b-1;j++){
            f[i][j]=-0x3f3f3f3f;
        }
        for(int j=b1+1;j<=m;j++){
            f[i][j]=-0x3f3f3f3f;
        }
        if(b!=1&&b1!=m){
            b--,b1++; 
        }
    }
    for(int i=1;i<=m;i++){
        mx=max(f[1][i],mx); 
    }
    cout<<mx;

    return 0;
}

 


1
康曦
康曦
中级光能
中级光能

要自上而下推(应该是)

1
薛乘志
薛乘志
初级启示者
初级启示者

我的思路:

将数组f全部置为极小值(防止算最大值时取到外面无关的值)

设置边界f[n+1][m/2+1]0(题目中“数据的出发点是最后一行的中间位置的下方”)

然后n,m双重倒序循环,f直接取上面、左上、右上最大值加上当前循环到的a元素(数塔)

再在所有i为1的数组f的值中取最大的一个输出(题目中“他决定从自己所处的位置吃到餐桌的另一侧”)

薛乘志在2021-11-24 20:25:53追加了内容

代码没有必要那么复杂...

0
0
0
我要回答