acw734 能量石

岩石怪物杜达生活在魔法森林中，他在午餐时收集了 N 块能量石准备开吃。

由于他的嘴很小，所以一次只能吃一块能量石。

能量石很硬，吃完需要花不少时间。

吃完第 i 块能量石需要花费的时间为 Si 秒。

杜达靠吃能量石来获取能量。

不同的能量石包含的能量可能不同。

此外，能量石会随着时间流逝逐渐失去能量。

第 i 块能量石最初包含 Ei 单位的能量，并且每秒将失去 Li 单位的能量。

当杜达开始吃一块能量石时，他就会立即获得该能量石所含的全部能量（无论实际吃完该石头需要多少时间）。

能量石中包含的能量最多降低至 0。

请问杜达通过吃能量石可以获得的最大能量是多少？

题目解读

1. 暴力枚举如何操作

需要枚举选了哪些能量石，并且按照怎样的顺序吃能量石

1. 贪心消除冗余

2. 使用邻项交换法，参考国王游戏

3. 对于任意的一个能量石序列而言，假设$i,j$是其中两块相邻的石头。如果对这两块能量石的位置进行交换，显然不会影响这两块能量石前面的能量石的能量，但对其后面的能量石的能量是否会产生影响呢？也不会，因为当这两块石头都被吃完后，在吃第三块石头之前，总共的时间并未发生改变，因此其后方所有的能量石的能量都未发生改变。

4. 这两块相邻的石头应该按照怎样的顺序排列呢？

   不妨假设，在刚要吃这两块石头中第一块石头的时刻，其能量分别为$E_i$与$E_j$，根据前面的讨论，$E_i,E_j$只与其在整个能量石序列中的位置有关，而于这两块石头谁先被吃无关。

   若先吃第$i$块，再吃第$j$块，这两块石头能够提供的能量为：

   $E_i+E_j-S_i*L_j$。

   若先吃第$j$块，再吃第$i$块，这两块石头能够提供的能量为：

   $E_i+E_j-S_j*L_i$

   若$i,j$的顺序比$j,i$更优（也即i应该在j的前面），则必有：

   $E_i+E_j-S_i*L_j>$$E_i + E_j - S_j * L_i$

   化简得到：

   $S_j * L_i > S_i * L_j$

5. 可以重载运算符，按照上述不等式的顺序对所有的能量石重新排列，那么至少能量石的顺序就确定了。

建模

1. 而后只需要考虑在一个给定的序列中如何挑选能量石，考虑0/1背包问题

2. 背包的物品数目即为能量石数目，背包的体积可以任意取，只要保证能量最大值所需的时间在体积范围内即可，另一种办法是将所有能量石所需时间加和。

3. 能量石的能量随着时间减少，但恰好0/1背包问题中有关于时间/体积的维度。因此为了准确表示吃能量石的时间，必须采用恰好0/1背包问题的思路，若为至少0/1背包，则吃能量石的时间是不准确的，即实际时间$\le$ 0/1背包的第二维

4. 注意$f[i][j]$表示考虑前i块能量石，并且时间恰为j的所有选法，因此在考虑第$i$块能量石时，其消耗的时间并非$j$，而是$j - S_i$，因为$j$是吃完第$i$块能量石的时刻。

5. 能量石的能量不能减到0，然鹅由于采取了恰好0/1背包，因此必定需要对从$[1,m]$的$f[j]$进行遍历，寻找最大值。若能量石的能量减到负数，显然还是小于最大值的，不会改变答案。

代码：

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

using namespace std;

const int N = 1e5 + 10;

int f[N];

int n, m;

struct STONE
{
    int s, e, l;
    bool operator<(const STONE &j)const &
    {
        return j.s * l > s * j.l;
    }
}stone[N];

int main(void)
{
    int t;
    cin >> t;
    for (int x = 1; x <= t; x++)
    {
        m = 0;
        memset(f, 0xc0, sizeof f);
        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            int s, e, l;
            cin >> s >> e >> l;
            stone[i] = {s, e, l};
            m += s;
        }
        sort(stone + 1, stone + 1 + n);
        f[0] = 0;
        for (int i = 1; i <= n; i++)
        {
            for (int j = m; j >= stone[i].s; j--)
            {
                f[j] = max(f[j], f[j - stone[i].s] + stone[i].e - (stone[i].l * (j - stone[i].s)));
            }
        }
        int res = 0;
        for (int i = 1; i <= m; i++)
            res = max(res, f[i]);
        printf("Case #%d: %d\n", x, res);
    }
    return 0;
}