自动搬运

查看原文

来自洛谷，原作者为

	2016jzy 为什么我那么菜啊qwq

搬运于2025-08-24 21:25:52，当前版本为作者最后更新于2016-08-25 21:26:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题跟数字金字塔的做法类似。。

只不过数字金字塔是往两条路线搜索，这题是往三条路线搜。。。

动态方程： f[i][j]=max(max(f[i-1][j],f[i-1][j-1]),f[i-1][j+1])+a[i][j];

#include<iostream>
#include<cstring>                             //头文件
using namespace std;
int n,m,a[201][201],f[201][201]={0},x,y;
int main()
{
    cin>>n>>m;
    y=m/2+1;x=n;                           //求出李大水牛最开始的位置
    memset(a,-9999,sizeof(a));               //设置边界，为了避免李大水牛吃到餐桌外面去。。
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];               //输入
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            f[i][j]=max(max(f[i-1][j],f[i-1][j-1]),f[i-1][j+1])+a[i][j];         //动态方程
        }
    }
    cout<<max(max(f[x][y],f[x][y-1]),f[x][y+1])<<endl;       //因为最大值只可能在李大水牛的前方、左前方、右前方，所以只要找这三个的最大就行了
    return 0;
}