题目描述
岩石怪物杜达生活在魔法森林中，他在午餐时收集了 $N$ 块能量石准备开吃。
由于他的嘴很小，所以一次只能吃一块能量石。
能量石很硬，吃完需要花不少时间。
吃完第 $i$ 块能量石需要花费的时间为 $S_i$ 秒。
杜达靠吃能量石来获取能量。
不同的能量石包含的能量可能不同。
此外，能量石会随着时间流逝逐渐失去能量。
第 $i$ 块能量石最初包含 $E_i$ 单位的能量，并且每秒将失去 $L_i$ 单位的能量。
当杜达开始吃一块能量石时，他就会立即获得该能量石所含的全部能量（无论实际吃完该石头需要多少时间）。
能量石中包含的能量最多降低至 $0$。
请问杜达通过吃能量石可以获得的最大能量是多少？
输入格式
第一行包含整数 $T$，表示共有 $T$ 组测试数据。
每组数据第一行包含整数 $N$，表示能量石的数量。
接下来 $N$ 行，每行包含三个整数 $S_i$,$E_i$,$L_i$。
输出格式
每组数据输出一个结果，每个结果占一行。
结果表示为 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我们直接开门见山
这里我先列举两个理解点：
- 不能直接枚举吃不吃每个石头，因为最终的收益还与吃的时机有关，不仅仅与吃不吃有关，假如一个能量石吃要很久，但是衰减的很慢，另一个能量石吃很快，衰减的很快，如果先考虑第一个能量石，即便吃了第二个能量石也变为0了，而如果不吃，又少了第一个能量石的能量，所以如果先吃2再吃1就两者皆可得
- 状态转移方程中，$e-(j-s)l<0$ 的理解：令 $t=e-(j-s)l<0$，如果 $dp[j-s]+t>dp[j]$，可以被能量值为0或负数的能量石更新。那么必然有 $dp[j-s]>=dp[j]$，这就存在一种情况是时间长的吃得所获得得能量还少，那么最终的最优解必然不会从这一轮的 $dp[j]$ 更新过来，因为这一轮的 $dp[j-s]$ 等于上一轮的 $dp[j-s]$ ，其值更大，时间更短。(注意一维方式是从大到小枚举时间 $j$ )
如何排序：
假设考虑第 $i$ 和第 $i+1$ 个能量石
先吃 $i$ 的可获得的能量：$$E_i+E_{i+1}-S_i*L_{i+1}$$.
先吃 $i+1$ 可获得的能量：$$E_i+E_{i+1}-S_{i+1}*L_i$$.
那么如果 $S_i*L_{i+1}<S_{i+1}L_i$ 即可获得的能量较大，如果不是，则先吃 $i+1$，
那么我们就可以根据这个排序了！
接下来就是01背包了
C++代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=110,M=100010;
struct Stone
{
int e,s,l;
bool operator < (const Stone &oo) const
{
return s*oo.l<oo.s*l;
}
}stone[N];
int n,dp[M];
int main()
{
int T; cin>>T;
for(int k=1;k<=T;k++)
{
cin>>n;
int m=0;
for(int i=0;i<n;i++)
{
cin>>stone[i].s>>stone[i].e>>stone[i].l;
m+=stone[i].s;
}
sort(stone,stone+n);
memset(dp,-0x3f,sizeof dp);
dp[0]=0;
for(int i=0;i<n;i++)
{
int s=stone[i].s,l=stone[i].l,e=stone[i].e;
for(int j=m;j>=s;j--)
if(e-(j-s)*l>0) //这一步可以没有，但是亲测加上快了100ms
dp[j]=max(dp[j],dp[j-s]+e-(j-s)*l);
}
int res=0;
for(int i=0;i<=m;i++) res=max(res,dp[i]);
printf("Case #%d: %d\n",k,res);
}
return 0;
}
test