二维动态规划 + 性质分析 | #三角形取数(Hard Version)#

分析

定义状态表示 $f_{i, j}$ 表示从 $(i, j)$ 到最后一行能得到的最大价值

为什么这么定义?

因为方便对题目的条件 $|r - l| < k$ 进行判断

从起点到最后一行向右移动了 $r$ , 向左移动了 $l$ , 设 $t = r - l$

那么最终到达最后一行的位置是 $j = n + t$

也就是 $t = j - n$ , 因此有约束条件 $|j - n| \le k$

因此只需要初始化最后一行的状态就能计算约束条件, 不需要额外判断

	for (int i = 1; i <= 2 * n - 1; ++i) {
		if (abs(i - n) > k) f[n][i] = -INF;
	}

代码实现

算法时间复杂度 $O(n ^ 2)$

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 610, MOD = 998244353;
const LL INF = 1e18;

int n, k;
int w[N][N];
LL f[N][N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

	cin >> n >> k;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= 2 * i - 1; ++j) {
			cin >> w[i][j];
			f[i][j] = w[i][j];
		}
	}

	for (int i = 1; i <= 2 * n - 1; ++i) {
		if (abs(i - n) > k) f[n][i] = -INF;
	}

	for (int i = n - 1; i >= 1; --i) {
		for (int j = 1; j <= 2 * i - 1; ++j) {
			LL maxv = max({f[i + 1][j], f[i + 1][j + 1], f[i + 1][j + 2]});
			if (maxv > -INF / 2) {
				f[i][j] += maxv;
			}
			else f[i][j] = -INF;
		}
	}

	cout << f[1][1] << '\n';
    return 0;
}