题解 | 三角形取数(Hard Version)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<vector<int>> vec;
    vector<vector<long long>>dp;
    for(int i=0;i<n;i++){
    vec.push_back(vector<int>(2*i+1,0));
    dp.push_back(vector<long long>(2*i+1,LLONG_MIN));
    }
    for(int i=0;i<n;i++)
    for(int j=0;j<2*i+1;j++)
    cin>>vec[i][j];
    dp[0][0]=vec[0][0];
    for(int i=1;i<n;i++)
        for(int j=0;j<2*i+1;j++)
            for(int l=max(0,j-2);l<=min(j,2*i-2);l++)
                dp[i][j]=max(dp[i][j],vec[i][j]+dp[i-1][l]);
    int index=n-1;
    for(int i=0;i<2*n-1;i++)
    if(dp[n-1][i]>dp[n-1][index]&&abs(n-1-i)<=k)
    index=i;
    cout<<dp[n-1][index];
}
// 64 位输出请用 printf("%lld")