链接:
Description
众所周知, 由于木星引力的影响, 世界各地的推进发动机都需要进行重启. 现在你接到紧急任务, 要去收集火石碎片, 重启西邮发动机.
现在火石碎片已成为了稀缺资源, 获得火石碎片需要钱或者需要一定的积分. 火石碎片有大有小, 越大的碎片能量越大, 火石碎片的能量越大, 重启的发动机的推力也就越强. 但是, 不只有我们在努力呀, 隔壁的师大和政法也都在收集碎片, 争取重启师大发动机和政法发动机, 哪个高校重启的发动机推力最大, 就能代表长安区大学城为世界做出贡献, 从而在史书上留下浓墨重彩的一笔.
现在你有 v1 块钱, v2 积分, 能免费 (免积分) 收集 k 个火石碎片, 现在总共有 n 个火石碎片, 每个碎片需要的钱 a 或者积分 b, 碎片的能量为 val. 我们希望收集火石碎片, 使能量的总和尽可能大, 问你 skyer_hxx 最多可以拿到能量总和的最大值是多少?
Input
输入包含多组测试用例.
每组数据的第一行是四个整数 n,v1,v2,k;
然后是 n 行, 每行三个整数 a,b,val, 分别表示每个碎片的价钱, 兑换所需积分, 所含能量.
1 ≤ n ≤ 100
0 ≤ v1,v2 ≤ 100
0 ≤ k ≤ 5
0 ≤ a,b,val ≤ 100
Output
对于每组数据, 输出能得到的最大能量值.
- Sample Input
- 4 5 2 1
- 2 2 4
- 4 5 1
- 4 2 4
- 2 2 5
- Sample Output
- 14
- Hint
只要钱或者积分满足购买一个碎片的要求, 那么就可以买下这个碎片.
题解思路:
1. 每块碎片只有一个, 典型的 01 背包变形问题.
2.dp[i][j][k]代表花费 i 元钱, j 积分, 免费换取 k 个碎片所能获得的最大价值.
3. 对于每个物品, 我们可以有 3 个选择: 花钱, 花积分, 免费换取. 因此四层循环, 判断 3 种选择, 更新最大值即可.
代码:
- #include<stdio.h>
- #include<string.h>
- #include<algorithm>
- #define mem(a, b) memset(a, b, sizeof(a))
- using namespace std;
- int n, v1, v2, k;
- int a[110], b[110], val[110];
- int dp[110][110][10]; // 代表花费 i 钱, j 积分和免费兑换 k 次所达到的最大价值
- int main()
- {
- while(scanf("%d%d%d%d", &n, &v1, &v2, &k) != EOF)
- {
- mem(dp, 0);
- for(int i = 1; i <= n; i ++)
- scanf("%d%d%d", &a[i], &b[i], &val[i]);
- for(int i = 1; i <= n; i ++)// 遍历每个碎片
- {
- for(int j = v1; j>= 0; j --)// 钱
- {
- for(int l = v2; l>= 0; l --)// 积分
- {
- for(int m = k; m>= 0; m --)// 免费兑换
- { // 枚举了每一种状态
- int temp = 0;
- if(j>= a[i])
- temp = max(temp, dp[j - a[i]][l][m] + val[i]);
- if(l>= b[i])
- temp = max(temp, dp[j][l - b[i]][m] + val[i]);
- if(m>= 1)
- temp = max(temp, dp[j][l][m - 1] + val[i]);
- dp[j][l][m] = max(temp, dp[j][l][m]);
- }
- }
- }
- }
- printf("%d\n", dp[v1][v2][k]);
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3075083.html