能量石

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

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

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

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

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

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

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

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

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

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

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

输入格式

第一行包含整数 T，表示共有 T 组测试数据。

每组数据第一行包含整数 N，表示能量石的数量。

接下来 N 行，每行包含三个整数 Si,Ei,Li。

输出格式

每组数据输出一个结果，每个结果占一行。

结果表示为 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时便不用花时间去吃。 性质1： 只吃能量还存在的石头 这个性质显而易见, 接下来就选两个石头看怎么选择 对于这两个石头都吃时所获得的能量有两个情况：

1. 先吃i后吃i+1 e[i] + e[i + 1] - s[i] * l[i + 1]
2. 先吃i+1后吃i e[i+1] + e[i] - s[i+1] * l[i] 显然, 这里有个最优选择, 选择 s 最小的那个先吃。

也就是说, 对于所有可行吃法, 最优解肯定符合, 吃的顺序是s[i] * l[i+1]从小到大的。 性质2： 吃石头的最优解中满足任意两个石头, 先吃的 s[i] * l[i + 1] < s[i + 1] * l[i]

那么我们就将所有石头排个序, 对于石头i, 不可能再从i之前的石头中得到比当前更优的解法, 故 f[i - 1] 是固定的, 不会因后续的新石头而变化 因此, 就跟01背包问题相类似了。

带入01背包的框架思考一下： 对于石头i有选和不选两种选择 选： f[i][j] = f[i - 1][j - s[i]] + e[i] - (j - s[i])*l[i]; 不选： f[i][j] = f[i - 1][j];

这样的话有个问题, 题目说开始吃的时候能量就不会减少了, 会不会出现能吃但因为时间不够而吃不了呢？ 并不会, 题目没有对吃的时间做限制, 也就是说, 哪怕当前的j时间吃不了, 之后也会更大的能吃得了的j。

如果对总时间做了约束, 会更复杂一些。

这里既然是01背包那么也能优化为一维。

初始化时应该初始化为负无穷, 时间恰好是j： 以前能算到至多是 j 是因为dp[0][j]都是0，即从i=0时从哪个体积开始都是合法的， 相当于把空余的体积加在了最前面，但现在这样不是最优,把空余时间加在最后面和最前面不一样。 多的时间会导致能量随时间减少。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110, T = 1e7 + 10;
int f[T];
int n;
 
struct Stone
{
    int s,e,l;
    bool operator < (const Stone &W)const
    {
        return s * W.l < W.s * l;
    }
}stone[N];
 
int main()
{
    int k, kase=0;
    cin >> k;
    while(k--)
    {
        int m = 0;
        cin >> n;
        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] + e - (j - s) * l);
                //cout << s << " " << e << " " << l << " " << f[j] <<  endl;
            }
                
        }
        
        int res = 0;
        for(int i = 0; i <= m; i++)
            res = max(res, f[i]);
        printf("Case #%d: %d\n", ++kase, res);
        
    }
    return 0;
}