塔子哥的快乐值-美团2023笔试(codefun2000)
题目链接
塔子哥的快乐值-美团2023笔试(codefun2000)
题目内容
塔子哥有许多生活琐事。已知他生活中有n个事件，解决第i个事件需要他花费ti的时间和hi的精力，并能获得ai 的快乐值。
塔子哥想知道，在总花费时间不超过T且总花费精力不超过H的前提下，塔子哥最多可以获得多少快乐值？
输入描述
输出描述
一个整数，代表塔子哥最多的快乐值。
样例1
输入
4
10 15
1 7 5
5 4 6
3 8 1
10 5 7
输出
11
题解1
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 510;int n, t, h, T[N],H[N],a[N];
LL dp[N][N];int main(){scanf("%d%d%d", &n, &t, &h);for(int i = 1; i <= n; i++) scanf("%d%d%d", &T[i], &H[i], &a[i]);// 多个约束条件的01背包 for(int i = 1; i <= n; i++){for(int j = t; j >= T[i]; j--){for(int k = h; k >= H[i]; k--){dp[j][k] = max(dp[j][k], dp[j - T[i]][k - H[i]] + a[i]);}}} printf("%lld\n", dp[t][h]);return 0;
}