零、前言

本蒟蒻不才，发布一个正常的第一想法

注：本题解仅代表本蒟蒻的个人意见，并无冒犯楼上楼下各位大佬的意思

一、输入

略

二、分析

1. dp数组状态设计

   设 $dp_{i,j,k}$ 为从最后一行正中间下方向前方移动 $i$ 格，向左前方移动 $j$ 格，向右前方移动 $k$ 格。

2. 不必要的 初始化

   $dp_{0,0,0}=a_{n+1,m/2+1}$

3. 状态转移

   到 $dp_{i,j,k}$ 时，最后一步可能走的是前方，左前方或右前方。

三、输出

输出的答案是餐桌最前端，即第一行的 $dp$ 最大值。

四、代码

#include <bits/stdc++.h>
using namespace std;
int n, m, a[205][205], dp[205][205][205], ans;
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            scanf("%d", &a[i][j]);
    dp[0][0][0] = a[n + 1][m / 2 + 1];                            //可省略
    for (int i = 0; i <= n; i ++)
        for (int j = 0; j <= n; j ++)
            for (int k = 0; k <= n; k ++)
            {
                if (i + j + k > n)                                //防止走出餐桌
                    continue;
                int x = n + 1 - i - j - k, y = m / 2 + 1 - j + k; //以下为状态转移
                if (i)
                    dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k] + a[x][y]);
                if (j)
                    dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][k] + a[x][y]);
                if (k)
                    dp[i][j][k] = max(dp[i][j][k], dp[i][j][k - 1] + a[x][y]);
                if (i + j + k == n)                               //如果移动到第一行，那么可能是答案
                    ans = max(ans, dp[i][j][k]);
            }
    printf("%d", ans);
    return 0;
}

#include <iostream>
using namespace std;
int main(void){
    int n,m,f[405][405]={};
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>f[i][j];             //因为f数组动态规划时不会管自己，为了方便就可以简化
    for(int i=2;i<=n+1;i++) //第一行不用管了，最后一行要取值
        for(int j=1;j<=m;j++)
            f[i][j]+=max(f[i-1][j-1],max(f[i-1][j],f[i-1][j+1]));
    cout<<f[n+1][m/2+1]; //输出最后一行的中间位置
    return 0;
}//已70分

https://static.hetaoimg.com/crmFiles/7f7db67bc76b4b19a1576bab0a37abaa.mp4

题解分析

看了别想满分