题解 | 【模板】二维费用背包

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

//相比一维多了一次循环一个状态，状态压缩还是和一维差不多，核心是确保本轮不会访问到已经更新的值，这个显然满足，因为只会访问小于当前状态的位置且当前的状态始终减小，绝对不可能访问本轮已经更新的位置
int main() {
	int n, t, h;
	cin >> n >> t >> h;
	long long** dp = new long long*[t + 1];
	for (int i = 0; i <= t; i++) {
		dp[i] = new long long[h + 1];
		memset(dp[i], 0, sizeof(long long) * (h + 1));
	}
	int *time = new int[n + 1], *high = new int[n + 1], *val = new int[n + 1]; 
	for (int i = 1; i <= n; i++) {
		cin >> time[i] >> high[i] >> val[i];
	}
	//滚动数组逆序遍历 
	for(int i = 1; i <= n; i++) {
		for (int j = t; j >= time[i]; j--) {
			for (int k = h; k >= high[i]; k--) {
				dp[j][k] = max(dp[j - time[i]][k - high[i]] +  val[i], dp[j][k]); 
			}
		}
	}
	cout << dp[t][h] << endl;
}