三维无脑dp

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N=110;
int dp[N][N][N],a[N][N];
int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            cin>>a[i][j];
    memset(dp,-1,sizeof(dp));
    dp[1][1][0]=a[1][1];
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            for(int k=0;k<=(n+1)/2;k++)
            {
                if(dp[i-1][j][k]!=-1)
                    dp[i][j][k+1]=max(dp[i][j][k+1],dp[i-1][j][k]+a[i][j]); // 正上转移而来
                if(dp[i-1][j-1][k]!=-1)
                    dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k]+a[i][j]); // 左上转移而来
            }
        }
    }
    for(int j=1;j<=n;j++)
    {
        for(int k=0;k<=(n+1)/2;k++)
        {
            int k1=n-1-k;
            if(abs(k-k1)<=1)mx=max(mx,dp[n][j][k]);
        }
    }
    printf("%d\n",mx);
    return 0;
}
/*
2
7
2 3
ans:10
*/