一：思路分析：

1：本题很巧很难，如果暴力的话，就是全排列的所有方案，肯定超时，然后我们考虑是否可以确定一个选择序列，首先说说贪心的问题，我们只考虑相邻的两个物品，i 和 i+1 这两个物品

先选i:   e(i) + e(i+1) - s(i)*l(i+1)
先选i+1：e(i) + e(i+1) - s(i+1)*l(i)

我们观察可以看出相邻的两个物品的最后一项不同，那么我们可以按照最后那项从小到大排个序，那么我们在选相邻的两个物品时优先选前面的一定比先选后面的优，这样就确定了一个序列，这个序列一定是全排列中最优的一个排列，最优解一定产生在这个序列中，所以接下来问题就变为在这个序列中如何找最优解

2：如何在这个序列找到最优解呢？暴力的话就是每个物品选和不选，可以看出有2^n的复杂度，也会超时，那么我们再想这个和 01 背包问题是不是一样呢，答案是一样的，但是这个“背包容量”这里是啥呢？

3：背包容量不是那么明显，我们去想一下这里把什么当作背包容量不会错过最优解，在处理第i件物品选不选的时候，如果选的话，第i件物品损失的能量就是从起点到第i-1件所花费的所有时间再乘上第i件物品的损失率，所以可以看出所花费的总时间就是“背包容量”，这里背包容量最大就是所有物品都选，把所有物品的时间加在一起

4：dp[j]：表示从前 i 件物品中选，当前已经花费了 j 那么长的时间的最大价值

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 10010;

struct store{
    int s, e, l;       
    bool operator< (const store& a){
        return s*(a.l) < l*(a.s);
    }
}stores[N];

int n;
int dp[N];

int main(){
    int T;cin >> T;
    int cnt = 1;

    while(T--){
        int m = 0;
        cin >> n;
        for(int i = 1;i <= n;++i) {
            cin >> stores[i].s >> stores[i].e >> stores[i].l;
            m += stores[i].s;
        }
        sort(stores+1, stores+1+n);

        memset(dp, -0x3f, sizeof dp);
        dp[0] = 0;
        //01 背包
        for(int i = 1;i <= n;++i)
            for(int j = m;j >= stores[i].s;--j)
                dp[j] = max(dp[j], dp[j-stores[i].s] + max(0, stores[i].e - (j-stores[i].s) * stores[i].l));

        int ans = 0;
        for(int j = 1;j <= m;++j) ans = max(ans ,dp[j]);

        cout << "Case #" << cnt++ << ":" << " " << ans << endl;
    }
}