算法

(贪心+01背包) $O(nm)$

此题个人认为最难想的地方莫过于贪心，为何要先进行贪心呢，或者说贪心的必要性是什么？
首先，此题想到01背包应该是不难的，因为这题无非就是对每一块石头进行选与不选的抉择。但光光进行这一步，答案显然是错误的，因为选到后面，可能会导致他们现有的能量变成0。前面所选的石头如果需要花费越长的时间吃，则后面石头所剩余的能量就越少，我们如果不进行贪心，则会造成前面的决策真的只是成了一个局部最优解，并且利用这个局部最优解，你无法构造出全局最优解。
为此我们需要利用贪心来缩小我们的决策范围。
根据下面的推导可以得到贪心的方式：

假设：
考虑相邻的两块石头：(吃的时间相邻)他们此时的能量为e1，e2
则先吃1可获得的能量：e1+e2-s1*l2
若先吃2可获得的能量：e1+e2-s2*l1
并且可以推导出：若a > b , b > c , 则a > c , 即他具有传递性。

为此我们得出了一个吃的先后顺序，但别忘了e1和e2还取决于初始能量。为此我们不得不进行01背包。

C++ 代码

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

using namespace std;

const int N = 110 , M = 10010;

struct Stone{
  int s , e , l ; //吃需要s秒，初始能力e，每秒消耗l
}stones[N];

bool cmp(const Stone& x , const Stone& y){
    return  x.s*y.l < y.s*x.l; 
}

int n , T ;
int f[N][M];

int main()
{
    cin >> T ;
    for(int cntT = 1 ; cntT <= T ;  cntT ++ ){
        cin >> n ;  
        int m = 0 ;
        for(int i = 1 ; i <= n ; i ++ ){
            int s , e , l ;
            cin >> s >> e >> l ;
            stones[i] = {s , e , l};
            m += s;
        }
        sort(stones+1 , stones+1+n , cmp);    //利用贪心把能量石最后不为0的尽可能的放在前面

        //贪心的必要性？

        //从前i块石头中选，吃j秒的最大价值

        //选第i块石头：f[i,j] = max(f[i-1,j] , f[i-1][j-s]+max(0,e-(j-s)*l)
        //不选第i块石头：f[i,j] = f[i-1,j]

        memset(f , 0 , sizeof f);
        for(int i = 1 ; i <= n ; i ++ )
            for(int j = 0 ; j <= m ; j++ ){
                f[i][j] = f[i-1][j] ;
                if( j >= stones[i].s ){
                    int s = stones[i].s , e = stones[i].e , l = stones[i].l ;
                    f[i][j] = max(f[i][j] , f[i-1][j-s] + max(0 , e-(j-s)*l) );   
                }
            }

        int ans = 0 ;
        for(int i = 0 ; i <= m ; i++ )  
            ans = max(ans , f[n][i]);

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

    return 0 ;
}