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

倒序dp。

(i, j)

↓ ↓ ↓

(i+1, j) (i+1, j+1) (i+1, j+2)。

注意约束|l-r|<=k。

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
using ll=long long;
const ll INF=-1e18;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    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 mid=n-1;
    for(int j=0;j<2*n-1;j++){
        if(abs(j-mid)>k)dp[n-1][j]=INF;
    }
    for(int i=n-2;i>=0;i--){
        for(int j=0;j<=2*i;j++){
            ll 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]<<endl;
    return 0;
}