$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

结论： $按\ \dfrac{s_i}{l_i}\ 从小到大排序$

证明：

$先吃第\ i\ 块能量石，再吃第\ i+1\ 块能量石，所得能量：e_i’+e_{i+1}’-s_i\cdot l_{i+1}$

$先吃第\ i+1\ 块能量石，再吃第\ i\ 块能量石，所得能量：e_{i+1}’+e_i’-s_{i+1}\cdot l_i$

$若让前者大于后者，则\ \dfrac{s_i}{l_i}<\dfrac{s_{i+1}}{l_{i+1}}$

可参考： 耍杂技的牛

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 110, M = 10010;

int n;
struct Stone
{
    int s,e,l;
    bool operator< (const Stone &W) const
    {
        return s*W.l<l*W.s;
    }
}stone[N];
int f[M]; //从前 i 个物品中选，体积恰好是 j 的最大价值

int main()
{
    int T;
    cin>>T;

    for(int Case=1;Case<=T;Case++)
    {
        cin>>n;

        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); //排序

        memset(f,0,sizeof f); //多组数据初始化

        // 01 背包
        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); // e - (j - s) * l 有可能是负数
        }

        int res=0;
        for(int i=0;i<=m;i++) res=max(res,f[i]); //找到最优解

        printf("Case #%d: %d\n",Case,res);
    }

    return 0;
}