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

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,k;
int a[305][605],dp[305][605];
//存在负数的用例，ans初始最大值不能是-1，必须是一个极小的负数
int l,r,ans=-4e18;
signed main() 
{
    cin>>n>>k;
    // 将整个dp数组初始化为极小的负数，表示该位置不可达
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=2*n;j++)
        {
            dp[i][j]=-4e18;
        }
    }
    for(int i=1;i<=n;i++)
    {
        int m=2*i-1;
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][n-i+j];
        }
    }
    dp[1][n]=a[1][n];
    for(int i=2;i<=n;i++)
    {
        int m=2*i-1;
        for(int j=1;j<=m;j++)
        {
            int col=n-i+j;
            dp[i][col] = max({dp[i-1][col-1], dp[i-1][col], dp[i-1][col+1]}) + a[i][col];
        }
    }
    for(int j=1;j<=2*n-1;j++)
    {
	  //题目要求的限制条件|l-r|<=k，在数学上完全等价于最终到达的列数|C-n|<=k满足！
        if(abs(j-n)<=k)
        {
            ans=max(ans,dp[n][j]);
        }
    }
    cout<<ans;
    return 0;
}