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