题目描述
岩石怪物杜达生活在魔法森林中，他在午餐时收集了N块能量石准备开吃。
由于他的嘴很小，所以一次只能吃一块能量石。
能量石很硬，吃完需要花不少时间。
吃完第 i 块能量石需要花费的时间为Si秒。
杜达靠吃能量石来获取能量。
不同的能量石包含的能量可能不同。
此外，能量石会随着时间流逝逐渐失去能量。
第 i 块能量石最初包含Ei单位的能量，并且每秒将失去Li单位的能量。
当杜达开始吃一块能量石时，他就会立即获得该能量石所含的全部能量（无论实际吃完该石头需要多少时间）。
能量石中包含的能量最多降低至0。
请问杜达通过吃能量石可以获得的最大能量是多少？
输入格式
第一行包含整数T，表示共有T组测试数据。
每组数据第一行包含整数N，表示能量石的数量。
接下来N行，每行包含三个整数Si,Ei,Li。
输出格式
每组数据输出一个结果，每个结果占一行。
结果表示为“Case #x: y”，其中x是组别编号（从1开始），y是可以获得的最大能量值。
数据范围
1≤T≤10,
1≤N≤100,
1≤Si≤100,
1≤Ei≤105,
0≤Li≤105
输入样例：
3
4
20 10 1
5 30 5
100 30 1
5 80 60
3
10 4 1000
10 3 1000
10 8 1000
2
12 300 50
5 200 0
输出样例：
Case #1: 105
Case #2: 8
Case #3: 500
样例解释
在样例＃1中，有N = 4个宝石。杜达可以选择的一个吃石头顺序是：
吃第四块石头。这需要5秒，并给他80单位的能量。
吃第二块石头。这需要5秒，并给他5单位的能量（第二块石头开始时具有30单位能量，5秒后失去了25单位的能量）。
吃第三块石头。这需要100秒，并给他20单位的能量（第三块石头开始时具有30单位能量，10秒后失去了10单位的能量）。
吃第一块石头。这需要20秒，并给他0单位的能量（第一块石头以10单位能量开始，110秒后已经失去了所有的能量）。
他一共获得了105单位的能量，这是能获得的最大值，所以答案是105。
在样本案例＃2中，有N = 3个宝石。
无论杜达选择吃哪块石头，剩下的两个石头的能量都会耗光。
所以他应该吃第三块石头，给他提供8单位的能量。
在样本案例＃3中，有N = 2个宝石。杜达可以：
吃第一块石头。这需要12秒，并给他300单位的能量。
吃第二块石头。这需要5秒，并给他200单位的能量（第二块石头随着时间的推移不会失去任何能量！）。
所以答案是500。
思路：贪心+01背包
贪心思路及证明
对于任意两个石头x1,x2，我们做出如下假设
①x1先吃，x2后吃,此时获得的能量高（可能相等）,那么就有
E1 + E2-L2*S1 > E1 + E2-L1*S2 ===> L1*S2<L2*S`1
移项得L1 / S1<L2/S2,此时我们只需要按照L1 / S1从小到大的顺序选择，获得的能量最大。如果不这样选取（即出现x2先选的情况），那么交换两个物品的选取顺序，获得的能量一定会更多（可能相等）。
01背包
所以我们可以利用贪心来对所有的能量石排序，这样问题就变成了按照一个线性顺序取对每一个能量石判断是否拿取的问题了，就变成了经典的01背包问题
还有一个是总时间 m的取值问题，因为我们状态定义的是前i个能量石中取，经过了恰好 j 时刻的解，所以只要找出 j 最大可能是多少就可以了，就是所有能量石时间总和
令f[i][j]为从前i个能量石中取，经过了恰好 j 时刻的解
状态转移方程
f[i][j] = max(f[i][j], f[i - 1][j - s] +e - l * (j - s));
由于我们不知道刚好进过哪一个时刻是解最大的时候 ，所以对每一个时间遍历，找出最大值
初始状态：f[0]=0f[0]=0，其余为负无穷
答案：max(f[i])(1<=i<=∑ni=1si)
代码
# include <iostream>
# include <algorithm>
# include <cstring>
using namespace std;
const int N = 10000;
int dp[N], e[N], s[N], l[N], idx[N];
bool cmp(int a, int b) {
return s[a] * l[b] < s[b] * l[a];
}
int main() {
int t, n;
cin >> t;
for (int C = 1; C <= t; C++) {
cin >> n;
int maxs = -1;
for (int j = 0; j < n; j++) {
cin >> s[j] >> e[j] >> l[j];
idx[j] = j;
maxs += s[j];
}
sort(idx, idx + n, cmp);
memset(dp, -0x3f, sizeof dp);
dp[0] = 0;
// for (int i = 1; i <= n; i ++) cout << 1.0 * s[idx[i]] / l[idx[i]] << endl;
for (int j = 0; j < n; j++) {
for (int k = maxs; k >= s[idx[j]]; k--) {
dp[k] = max(dp[k], dp[k - s[idx[j]]] + e[idx[j]] - (k - s[idx[j]]) * l[idx[j]]);
}
}
int res = 0;
for (int i = 0; i <= maxs; i++) res = max(res, dp[i]);
printf("Case #%d: %d
", C, res);
}
return 0;
}