<—点个赞吧QwQ

宣传一下算法提高课整理{:target=”_blank”}

岩石怪物杜达生活在魔法森林中，他在午餐时收集了$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 \\le T \\le 10$,
$1 \\le N \\le 100$,
$1 \\le S_i \\le 100$,
$1 \\le E_i \\le 10^5$,
$0 \\le L_i \\le 10^5$

输入样例：

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$。

思路

如果魔法石不会损失能量，就是一道$0/1$背包的裸题
但是以往的$0/1$背包每个物品的价值是不变的，因此我们可以指定任意的次序进行线性$dp$求解
但是本题魔法石会损失能量
因此如何枚举物品的次序是首要解决的问题，然后才可以套用$0/1$背包模型求解
我们这里采用贪心思路，从分析贪心解中两个相邻物品的次序来入手，假设在贪心解中存在$stone_i,stone_j$满足$j=i+1$且枚举到$stone_j$时，能量都不为$0$，如果能量为$0$，那么他们的次序可以任意安排，则存在如下不等式（次序$\overline{x,x,i,j,x,x}$获得的价值大于等于$\overline{x,x,j,i,x,x}$获得的价值）$E_i+E_j−S_i×L_j≥E_j+E_i−S_j×L_i\Rightarrow S_j×L_i≥S_i×L_j$
于是对于最优解中所有$S_j×L_i<S_i×L_j$的物品次序，我们都可以通过一次邻项交换的操作变成我们上述的次序，且保证该次交换完成后，总价值不减少
于是得以证明出贪心解$≥$最优解
而由于贪心解本就是合法解，因此自然而然贪心解$≤$最优解
得证：贪心解$=$最优解

代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 110,M = 100010;
int test_case = 1;
int n,m;
struct node {
    int s,e,l;
}a[N];
int f[M];
int main () {
    int T;
    cin >> T;
    while (T--) {
        memset (f,-0x3f,sizeof (f));
        f[0] = m = 0;
        cin >> n;
        for (int i = 1;i <= n;i++) {
            cin >> a[i].s >> a[i].e >> a[i].l;
            m += a[i].s;
        }
        sort (a + 1,a + 1 + n,[](node x,node y) {
            return x.s * y.l < x.l * y.s;
        });
        for (int i = 1;i <= n;i++) {
            for (int j = m;j >= a[i].s;j--) f[j] = max (f[j],f[j - a[i].s] + a[i].e - (j - a[i].s) * a[i].l);
        }
        int ans = 0;
        for (int i = 0;i <= m;i++) ans = max (ans,f[i]);
        cout << "Case #" << test_case++ << ": " << ans << endl;
    }
    return 0;
}