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

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

using ui=unsigned int;
using ll=long long;
using ull=unsigned long long;
using i128=__int128_t;
using u128=__uint128_t;
using ld=long double;

const ll INF=-1e18;

void solve()
{//dp[i][j]表示以i,j为起点往下移动能获得的最大值 由于这道题会在原数组上进行dp 我们可以直接将原数组当作dp数组
//从最后一行向上开始递推 最后的dp[0][0]即为答案 比从上向下要好
//题中所述|l-r|<=k等价于来到最后一行时 不能偏离中心点超过k 所以在最后一行中 超过这个范围的我们设为INF
//向上递推的过程中 如果dp[i][j]下面的三个值都为INF 则证明这条路不可行 于是将dp[i][j]也设为INF 下次经过这条路时 就知道不能走
	int n,k;
	cin >> n >> k;
	vector<vector<ll>>dp(n);
	for(int i=0;i<n;i++)
	{
		dp[i].resize(2*i+1);
		for(int j=0;j<dp[i].size();j++)
		{
			cin >> dp[i][j];
		}
	}
	for(int i=0;i<2*n-1;i++)
	{
		if(abs(i-n+1)>k) dp[n-1][i]=INF;
	}
	for(int i=n-2;i>=0;i--)
	{
		for(int j=0;j<=2*i;j++)
		{
			if(max(max(dp[i+1][j],dp[i+1][j+1]),dp[i+1][j+2])>INF)
			{
				dp[i][j]+=max(max(dp[i+1][j],dp[i+1][j+1]),dp[i+1][j+2]);
			}
			else
			{
				dp[i][j]=INF;
			}
		}
	}
	cout << dp[0][0];
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t=1;
	//cin >> t;
	
	while(t--)
	{
		solve();
	}
	return 0;
}