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

假设题目没有T这个约束，则这道题目可以看做 01 背包模板问题，所以我们只需要在 01 背包的基础上添加一层循环用来表示 T 的约束就可以了，dp[t][h] 表示在耗费t分钟和h点精力的情况下所收获的最大快乐值。

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

const int N = 550;
int dp[N][N];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0) , cout.tie(0);
    int n;
    cin >> n;
    int T , H;
    cin >> T >> H;
    for(int i = 1 , t , h , a ; i <= n ; i ++){
        cin >> t >> h >> a;
        for(int j = T ; j >= t ; j --)
            for(int k = H ; k >= h ; k --)
                dp[j][k] = max(dp[j][k] , dp[j - t][k - h] + a);
    }
    cout << dp[T][H] << '\n';
    return 0;
}