单调队列优化 $O(NW)$

#include <bits/stdc++.h>
using namespace std;
long long f[505][10005];
int W, n, L[505], R[505], V[505];

int main() {
	cin >> W >> n;
	for (int i = 1; i <= n; i++)
		cin >> L[i] >> R[i] >> V[i];
	memset(f, -1, sizeof f);
	f[0][0] = 0;
	for (int i = 1; i <= n; i++) {
		deque<int> que;
		for (int j = 0; j <= W; j++) {
			f[i][j] = f[i-1][j];
//			for (int k = max(0, j-R[i]); k <= j-L[i]; k++)
//				if (f[i-1][k] != -1)
//					f[i][j] = max(f[i][j], f[i-1][k] + V[i]);
			int k = j - L[i];
			if (k < 0 || f[i-1][k] == -1)
				;
			else {
				while (!que.empty() && f[i-1][que.back()] <= f[i-1][k])
					que.pop_back();
				que.push_back(k);
			}
			while (!que.empty() && que.front() < j - R[i])
				que.pop_front();
			if (!que.empty())
				f[i][j] = max(f[i][j], f[i-1][que.front()] + V[i]);
		}
	}
	cout << f[n][W] << endl;
	return 0;
}

$O(N W^2)$ 会TLE

#include <bits/stdc++.h>
using namespace std;
long long f[505][10005];
int W, n, L[505], R[505], V[505];

int main() {
	cin >> W >> n;
	for (int i = 1; i <= n; i++)
		cin >> L[i] >> R[i] >> V[i];
	memset(f, -1, sizeof f);
	f[0][0] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= W; j++) {
			f[i][j] = f[i-1][j];
			for (int k = max(0, j-R[i]); k <= j-L[i]; k++)
				if (f[i-1][k] != -1)
					f[i][j] = max(f[i][j], f[i-1][k] + V[i]);
		}
	}
	cout << f[n][W] << endl;
	return 0;
}