题目描述
岩石怪物杜达生活在魔法森林中，他在午餐时收集了 NN 块能量石准备开吃。
由于他的嘴很小，所以一次只能吃一块能量石。
能量石很硬，吃完需要花不少时间。
吃完第 \(i\) 块能量石需要花费的时间为 \(S_i\) 秒。
杜达靠吃能量石来获取能量。
不同的能量石包含的能量可能不同。
此外，能量石会随着时间流逝逐渐失去能量。
第 \(i\) 块能量石最初包含 \(E_i\) 单位的能量，并且每秒将失去 \(L_i\) 单位的能量。
当杜达开始吃一块能量石时，他就会立即获得该能量石所含的全部能量（无论实际吃完该石头需要多少时间）。
能量石中包含的能量最多降低至 0。
请问杜达通过吃能量石可以获得的最大能量是多少？
范围
\(1≤T≤10\)
\(1≤N≤100\)
\(1≤S_i≤100\)
\(1≤E_i≤10^5\)
\(0≤L_i≤10^5\)
题解
本题难点在于如何选择能量石的顺序。
假设我们能量石的最优序列为\(a_1,a_2,...,a_k\)
那么，交换第\(i\)和第\(j\)个可得：
\(E_i + (E_j - L_j \times S_i) \leq E_j + (E_i - L_i \times S_j)\)
化简得：
\(S_i \times L_j \leq S_j \times L_i\)
这样我们就得到了排序方式，可知最优解一定按这样的顺序出现。
之后就转化为01背包问题，设\(f_t\)表示用了\(t\)时间能获得的最大能量，计算即可.
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
const int S = 10010;
struct node {
int S,L;
int E;
}s[N];
bool cmp(node a,node b) {
return a.S * b.L <= a.L * b.S;
}
int f[S];
int t;
int T,n;
int cas;
int main () {
cin >> T;
while(T --) {
cin >> n;
t = 0;
memset(f,-0x3f,sizeof f);
for(int i = 1;i <= n; ++i) {
cin >> s[i].S >> s[i].E >> s[i].L;
t += s[i].S;
}
sort(s + 1,s + n + 1,cmp);
f[0] = 0;
for(int i = 1;i <= n; ++i) {
for(int j = t;j >= s[i].S; --j) {
f[j] = max(f[j],f[j - s[i].S] + max(0,s[i].E - (j - s[i].S) * s[i].L));
}
}
int res = 0;
for(int i = 1;i <= t; ++i) res = max(res,f[i]);
printf("Case #%d: %d\n",++cas,res);
}
return 0;
}