题目地址：
/problem/content/736/
岩石怪物杜达生活在魔法森林中，他在午餐时收集了 N N N块能量石准备开吃。由于他的嘴很小，所以一次只能吃一块能量石。能量石很硬，吃完需要花不少时间。吃完第 i i i块能量石需要花费的时间为 S i S_i Si秒。杜达靠吃能量石来获取能量。不同的能量石包含的能量可能不同。此外，能量石会随着时间流逝逐渐失去能量。第 i i i块能量石最初包含 E i E_i Ei单位的能量，并且每秒将失去 L i L_i Li单位的能量。当杜达开始吃一块能量石时，他就会立即获得该能量石所含的全部能量（无论实际吃完该石头需要多少时间）。能量石中包含的能量最多降低至 0 0 0。请问杜达通过吃能量石可以获得的最大能量是多少？
输入格式：
第一行包含整数 T T T，表示共有 T T T组测试数据。每组数据第一行包含整数 N N N，表示能量石的数量。接下来 N N N行，每行包含三个整数 S i , E i , L i S_i,E_i,L_i Si,Ei,Li。
输出格式：
每组数据输出一个结果，每个结果占一行。结果表示为Case #x: y，其中 x x x是组别编号（从 1 1 1开始）， y y y是可以获得的最大能量值。
数据范围：
1 ≤ T ≤ 10 1≤T≤10 1≤T≤10
1 ≤ N ≤ 100 1≤N≤100 1≤N≤100
1 ≤ S i ≤ 100 1≤S_i≤100 1≤Si≤100
1 ≤ E i ≤ 105 1≤E_i≤105 1≤Ei≤105
0 ≤ L i ≤ 105 0≤L_i≤105 0≤Li≤105
设集合 U U U表示所有这样的吃法，这些吃法的所有能量石都会被吃，而不会由于时间衰减而能量变成 0 0 0（比如在吃第 2 2 2个能量石吃完之后，结果第 5 5 5个能量石由于时间衰减而能量变成 0 0 0了，这种吃法就不会在集合 U U U里。显然 U U U已经包含了所有的吃法了，对于不满足 U U U的条件的吃法，我们只需要去掉那些衰减为 0 0 0的能量石即可。所以以下我们只考虑 U U U里的吃法）。我们任取 U U U的一种吃法，其吃能量石的顺序里，考虑第 i i i个和第 i + 1 i+1 i+1个能量石。设开始吃第 i i i个能量石的时候，第 i i i和 i + 1 i+1 i+1个能量石的能量是 e i e_i ei和 e i + 1 e_{i+1} ei+1，那么这两块能量石产生的贡献是 e i + max { 0 , e i + 1 − s i l i + 1 } = e i + e i + 1 − s i l i + 1 e_i+\max\{0,e_{i+1}-s_il_{i+1}\}=e_i+e_{i+1}-s_il_{i+1} ei+max{0,ei+1−sili+1}=ei+ei+1−sili+1（因为这种吃法属于 U U U，所以第 i + 1 i+1 i+1个能量石不会衰减成 0 0 0），如果交换这两个能量石的顺序，则它们的贡献是 e i + 1 + max { 0 , e i − s i + 1 l i } e_{i+1}+\max\{0,e_i-s_{i+1}l_i\} ei+1+max{0,ei−si+1li}。我们尝试找出一种贪心顺序，使得按照这种顺序的吃法是最优的。如果交换这两个能量石之后，形成的新吃法仍然属于 U U U，那么就有交换后的贡献 e i + 1 + e i − s i + 1 l i e_{i+1}+e_i-s_{i+1}l_i ei+1+ei−si+1li；如果原顺序是最优的，那么就有 e i + e i + 1 − s i l i + 1 ≥ e i + 1 + e i − s i + 1 l i ⇔ s i l i + 1 ≤ s i + 1 l i e_i+e_{i+1}-s_il_{i+1}\ge e_{i+1}+e_i-s_{i+1}l_i\Leftrightarrow s_il_{i+1}\le s_{i+1}l_i ei+ei+1−sili+1≥ei+1+ei−si+1li⇔sili+1≤si+1li，在能量石这个集合上定义一个偏序，能量石 A 1 ≤ A 2 ⇔ l 1 s 1 ≥ l 2 s 2 A_1\le A_2\Leftrightarrow \frac{l_1}{s_1}\ge \frac{l_2}{s_2} A1≤A2⇔s1l1≥s2l2（显然它也是个全序关系），我们猜测，按照这种偏序从小到大排序下的吃法是最优的。我们只需证明： s i l i + 1 ≥ s i + 1 l i ⇒ e i + e i + 1 − s i l i + 1 ≤ e i + 1 + max { 0 , e i − s i + 1 l i } s_il_{i+1}\ge s_{i+1}l_i\Rightarrow e_i+e_{i+1}-s_il_{i+1}\le e_{i+1}+\max\{0,e_i-s_{i+1}l_i\} sili+1≥si+1li⇒ei+ei+1−sili+1≤ei+1+max{0,ei−si+1li}因为这意味着对于 U U U里的某种最优吃法，一定可以将其适当做适当调整，使得其变成按上述偏序有序的吃法，并且不会使得结果更差，也就证明了按照上述偏序有序的吃法是最优的。证明如下：
1、如果 max { 0 , e i − s i + 1 l i } = e i − s i + 1 l i \max\{0,e_i-s_{i+1}l_i\}=e_i-s_{i+1}l_i max{0,ei−si+1li}=ei−si+1li，这个显然；
2、如果 max { 0 , e i − s i + 1 l i } = 0 \max\{0,e_i-s_{i+1}l_i\}=0 max{0,ei−si+1li}=0，那么相当于要证明 e i + e i + 1 − s i l i + 1 ≤ e i + 1 + max { 0 , e i − s i + 1 l i } = e i + 1 e_i+e_{i+1}-s_il_{i+1}\le e_{i+1}+\max\{0,e_i-s_{i+1}l_i\}=e_{i+1} ei+ei+1−sili+1≤ei+1+max{0,ei−si+1li}=ei+1，即要证 e i ≤ s i l i + 1 e_i\le s_il_{i+1} ei≤sili+1，即 e i − s i + 1 l i ≤ s i l i + 1 − s i + 1 l i e_i-s_{i+1}l_i\le s_il_{i+1}-s_{i+1}l_i ei−si+1li≤sili+1−si+1li，而 e i − s i + 1 l i ≤ 0 , s i l i + 1 ≥ s i + 1 l i e_i-s_{i+1}l_i\le 0,s_il_{i+1}\ge s_{i+1}l_i ei−si+1li≤0,sili+1≥si+1li，所以也成立。
注意，即使做交换后的吃法不在 U U U里了，仍然可以将衰减成 0 0 0的能量石去掉来让新吃法还属于 U U U，并且新吃法的逆序数会变小（或者不变）。
由上面知，我们只需要考虑 U U U里按上述偏序有序的吃法即可。这就可以用动态规划解决了。这是个经典的 0 − 1 0-1 0−1背包问题。设 f [ i ] [ j ] f[i][j] f[i][j]是只吃前 i i i个石头，总耗时恰好是 j j j的情况下的最大能量，则有 f [ 0 ] [ 0 ] = 0 , f [ 0 ] [ . > 0 ] = − ∞ f[0][0]=0,f[0][.>0]=-\infty f[0][0]=0,f[0][.>0]=−∞，并且： f [ i ] [ j ] = max { f [ i − 1 ] [ j ] , f [ i − 1 ] [ j − s i ] + max { 0 , e i − ( j − s i ) l i } } f[i][j]=\max\{f[i-1][j],f[i-1][j-s_i]+\max\{0,e_i-(j-s_i)l_i\}\} f[i][j]=max{f[i−1][j],f[i−1][j−si]+max{0,ei−(j−si)li}}最后只需返回 max j f [ N ] [ j ] \max_j f[N][j] maxjf[N][j]即可。之所以不把状态定义为总耗时恰好是 j j j的情况下的最大能量，是因为递推方程在这种情况下不好写，它并不能写成如上的形式，因为上面的方程实际上是在 j − s i j-s_i j−si的时刻才开始吃第 i i i个石头，但是实际最优方案应该是尽量安排在更早的时候吃（能量损耗少），而这个状态是很难写出转移方程的。所以就将状态定义为恰好总耗时是 j j j，这里的 j j j实际上是吃完最后一个石头的那一刻的时间。代码如下：
#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 10010;int n;struct Stone {int s, e, l;// 要重新定义石头的比较函数，最好写成乘法，以求精确性，并且避免0作为除数bool operator<(const Stone& T) const {return s * T.l < l * T.s;}} stone[N];// 为了空间优化，可以只开一维数组int f[N];int main() {int T;cin >> T;for (int C = 1; C <= T; C++) {cin >> n;// m存总耗时，其范围是从0到si的总和int m = 0;for (int i = 0; i < n; i++) {int s, e, l;cin >> s >> e >> l;stone[i] = {s, e, l};m += s;}sort(stone, stone + n);memset(f, -0x3f, sizeof f);f[0] = 0;for (int i = 0; i < n; i++) {int s = stone[i].s, e = stone[i].e, l = stone[i].l;for (int j = m; j >= s; j--) f[j] = max(f[j], f[j - s] + max(0, e - (j - s) * l));}int res = 0;for (int i = 0; i <= m; i++) res = max(res, f[i]);printf("Case #%d: %d\n", C, res);}return 0;}
对于每个case时间复杂度 O ( N ∑ S i ) O(N\sum S_i) O(N∑Si)，空间 O ( ∑ S i ) O(\sum S_i) O(∑Si)。
当然状态依然可以换种定义，使得上面的转移方程仍然正确。可以将 f [ i ] [ j ] f[i][j] f[i][j]定义为只从前 i i i个石头里选，并且所有石头都是在以 j j j结尾的某个连续区间吃完的方案中能量最大值（也就是说这些方案是，可能他先等一会儿时间，然后连续开吃若干个能量石并且中间不暂停，到 j j j时刻恰好吃完）。这样的话以下转移方程确实是对的： f [ i ] [ j ] = max { f [ i − 1 ] [ j ] , f [ i − 1 ] [ j − s i ] + max { 0 , e i − ( j − s i ) l i } } f[i][j]=\max\{f[i-1][j],f[i-1][j-s_i]+\max\{0,e_i-(j-s_i)l_i\}\} f[i][j]=max{f[i−1][j],f[i−1][j−si]+max{0,ei−(j−si)li}}但是这里要返回答案的时候仍然要返回 max j f [ N ] [ j ] \max_j f[N][j] maxjf[N][j]，因为最优解应当是他不等待，而是要一上来就开始吃，所以我们依然要遍历 j j j。初始值是 ∀ j , f [ 0 ] [ j ] = 0 \forall j,f[0][j]=0 ∀j,f[0][j]=0。代码如下：
#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 10010;int n;struct Stone {int s, e, l;bool operator<(const Stone& T) const {return s * T.l < l * T.s;}} stone[N];int f[N];int main() {int T;cin >> T;for (int C = 1; C <= T; C++) {cin >> n;int m = 0;for (int i = 0; i < n; i++) {int s, e, l;cin >> s >> e >> l;stone[i] = {s, e, l};m += s;}sort(stone, stone + n);memset(f, 0, sizeof f);for (int i = 0; i < n; i++) {int s = stone[i].s, e = stone[i].e, l = stone[i].l;for (int j = m; j >= s; j--) f[j] = max(f[j], f[j - s] + max(0, e - (j - s) * l));}int res = 0;for (int i = 0; i <= m; i++) res = max(res, f[i]);printf("Case #%d: %d\n", C, res);}return 0;}
时空复杂度一样。
