题目描述

想了一段时间终于想明白了，这题有以下几个要点：
1. dp之前要贪心，把每个石头按S/L排序，这样保证每次选的石头都是最优的
2. fij表示”恰好”用了j时间获得的能量，而不是”不超过”j时间获得的能量，原因如下

原因：

若fij代表”不超过”j时间获得的能量的话，如果在0-k时间内不吃石头，或者吃了能量为0的石头，在k-j时间内再吃石头i的话，这样石头i的能量会在0-k时间内白白流失，这样不是最优解

AC代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=10010;

int f[N];

struct Stone
{
    int s,e,l;
    bool operator< (const Stone &W)const
    {
        return s*W.l<l*W.s;
    }

}stone[N];

int main()
{
    int T;
    cin>>T;
    int P=T;
    while(T--)
    {
        int p=P-T;
        int n;
        cin>>n;
        int m=0;
        for(int i=1;i<=n;i++)
        {
            int a,b,c;
            cin>>a>>b>>c;
            stone[i]={a,b,c};
            m=m+a;
        }
        sort(stone+1,stone+1+n);

        //"恰好"的初始化方法
        memset(f,-0x3f,sizeof f);
        f[0]=0;
        for(int i=1;i<=n;i++)
        {
            int s=stone[i].s;
            int e=stone[i].e;
            int l=stone[i].l;
            for(int j=m;j>=s;j--)
            {
                //在第j-s时刻，用时s吃这个石头
                //因此该石头在此之前流失了(j-s)*l的能量
                f[j]=max(f[j],f[j-s]+e-(j-s)*l);
            }
        }
        int res=0;
        for(int i=0;i<=m;i++)
        res=max(res,f[i]);

        cout<<"Case #"<<p<<": "<<res<<endl;
    }

    return 0;
}