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

#include<bits/stdc++.h>
using namespace std;
const long long INF = -1e18;
#define ll long long
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,k;
    cin >> n >> k;
    vector<vector<ll>> a(n);
    for(int i=0; i<n; i++){
        a[i].resize(2*i+1);
        for(int j=0; j<2*i+1; j++){
            cin >> a[i][j];
        }
    }
    vector<vector<ll>> dp = a;
    int cen = n-1;
    for(int j=0; j<2*n-1; j++){
        if(abs(j-cen) > k){
            dp[n-1][j] = INF;
        }
    }
    for(int i=n-2; i>=0; i--){
        for(int j=0; j<2*i+1; j++){
            long long max_next = max({dp[i+1][j], dp[i+1][j+1], dp[i+1][j+2]});
            if(max_next > INF+1) dp[i][j] += max_next;
            else dp[i][j] = INF;
        }
    }
    cout << dp[0][0];
}