$\LARGE\color{orange}{刷题日记(算法提高课)}$

我们先考虑对于相邻两个能量石，以不同的顺序吃导致的结果如何

设相邻两块能量石为 $i$ 和 $i+1$

如果先吃 $i$ 后吃 $i+1$，此时获得的能量为 $E_i+E_{i+1}-S_i\times L_{i+1}$

如果先吃 $i+1$ 后吃 $i$，此时获得的能力为 $E_{i+1}+E_i-S_{i+1}\times L_i$

如果 $S_i\times L_{i+1} \lt S_{i+1}\times L_i$ ，那么前者所获能量一定大于后者

也就是说，如果按照 $S_i\times L_{i+1} \lt S_{i+1}\times L_i$ 并且从前往后的顺序吃，一定比按照其他顺序吃所获得的能量要大

此时我们便将这个问题转换为了一个 01 背包问题，$f[i][j]$ 表示集合为：考虑前 $i$ 个能量石，当消耗时间恰好为 $j$ 时，所获得的最大能量

这里我们的消耗时间必须是一个确定的数，不能出现大于或小于的情况

状态转移方程为 $f[i][j]=max(f[i-1][j],f[i-1][j-S_i]+E_i-(j-S_i)\times L_i)$

如果吃掉第 $i$ 个能量石的话，前面已经用掉了 $j-S_i$ 的时间，因此需要乘上这个系数

由于需要对每个能量石进行排序，因此我们直接用结构体来存储，然后通过重载运算符的方式来实现排序

注：这道题的 $N$ 需要给到 $10^5$ ，因为 $j$ 表示的是时间，因此时间最大可以取到 $10^5$

完整代码：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10010;

int f[N];
int n;
struct Stone
{
    int s, e, l;
    bool operator<(const Stone& S) const
    {
        return s * S.l < S.s * l;
    }
}stone[N];

int main()
{
    int T;
    cin >> T;
    for(int C = 1; C <= T; C++)
    {
        cin >> n;
        memset(f, -0x3f, sizeof f);
        f[0] = 0;
        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);
        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 ans = 0;
        for(int i = 0; i <= m; i++) ans = max(ans, f[i]);
        cout << "Case #" << C << ": " << ans << endl;
    }
    return 0;
}