AcWing 734 能量石

题目传送门

一、贪心（微扰）

这道题还是比较难的，前置知识：

贪心的微扰（邻项交换）证法，例题：，

观察发现，其选择的能量石有可能仅为部分能量石，而确定了组合之后我们要确定其排列，因为同几种能量石其排列的不同有可能影响其收益。

假定当前所选的能量石为\(k\)个，考虑怎样的排列是最优的。

对于任一排列\(a_1,a_2,a_3,…a_k\)
考虑任两项\(a_i,a_{i+1}\)
其交换后，不影响其他能量石的收益。

假定收集完第\(i?1\)块能量石时是第\(k\)秒，考虑交换前和交换后的收益：

交换前：
\(E_i?kL_i+E_{i+1}?(k+S_i)L_{i+1}=E_i+E_{i+1}?(kL_i+(k+S_i)L_{i+1})\)

交换后：
\(E_{i+1}?kL_{i+1}+E_i?(k+S_{i+1})L_i=E_i+E_{i+1}?(kL_{i+1}+(k+S_{i+1})L_i)\)

因此，我们只需要比较
\(kL_i+(k+S_i)L_{i+1},kL_{i+1}+(k+S_{i+1})L_i\) 的大小
且
\(kL_i+(k+S_i)L_{i+1}=k(L_i+L_{i+1})+S_iL_{i+1}\)

\(kL_{i+1}+(k+S_{i+1})L_i=k(L_i+L_{i+1})+S_{i+1}L_i\)

因此要比较的即
\(S_iL_{i+1},S_{i+1}L_i\)

交换前更优，即
\(S_iL_{i+1}≤S_{i+1}L_i\)

交换后更优，即：
\(S_iL_{i+1}≥S_{i+1}L_i\)

因此直接按\(S_iL_{i+1},S_{i+1}L_i\)排序即可。

因此，对于任一种组合我们是能唯一确定一种最大的排列的。

因此，直接在排序后做\(01\)背包即可。

二、01背包

背包问题有三种形态：,本题是哪种呢？
因为在不同时刻吃所能吸收的能量是不同的，而且每块能量石从最开始就在损失能量。所以能量的价值和时间是相关的，如果剩余空间长大，未必就一定划算，这就说明剩余空间需要一个精确值，而不能表示一个范围，所以是恰好。

• 占用的空间：\(q[i].s\)

• 获得的价值:\(max(0, q[i].e - (j - q[i].s) * q[i].l)\) (\(j\)为当前花费时长)。

\(f[j]\) 表示当前恰好花\(j\)时间得到的最大能量。

• 状态转移方程：

\(f[j] = max(f[j], f[j - q[i].s] + max(0, q[i].e - (j - q[i].s) * q[i].l))\)

由于我们背包放物品（宝石）的顺序是坐标从\(1\)到\(n\)的，所以一定能枚举到最优解。

初始状态：\(f[0]=0\)，其余为负无穷(因为是求最大值)

答案：\(max(f[i])\)

二、实现代码

#include 

using namespace std;
const int N = 110;  //能量石个数上限
const int M = 10010;//

//用来描述每个能量石的结构体
struct Node {
    int s;           //吃掉这块能量石需要花费的时间为s秒
    int e;           //可以获利e个能量
    int l;           //不吃的话，每秒失去l个能量
} q[N];              //能量石的数组,其实这里开的数组开的特别大了，题目中说是110就够了。

//结构体对比函数
bool cmp(const Node &a, const Node &b) {
    return a.s * b.l < b.s * a.l;
}

int n;               //能量石的数量
int f[M];            //f[i]:花i个时间得到的最大能量
int idx;             //输出是第几轮的测试数据

int main() {
    //优化输入
    ios::sync_with_stdio(false);
    //T组测试数据
    int T;
    cin >> T;
    while (T--) {
        //初始化为负无穷 -0x3f---> -1044266559
        memset(f, -0x3f, sizeof f);
        cin >> n;
        //总时长,背包容量
        int m = 0;
        //读入数据
        for (int i = 1; i <= n; i++) {
            cin >> q[i].s >> q[i].e >> q[i].l;
            m += q[i].s;
        }
        //贪心排序
        sort(q + 1, q + 1 + n, cmp);

        //01背包,注意恰好装满时的状态转移方程的写法
        //更形象的理解方法看一下潜水员那道题。
        f[0] = 0;
        for (int i = 1; i <= n; i++)
            for (int j = m; j >= q[i].s; j--)
                f[j] = max(f[j], f[j - q[i].s] + max(0, q[i].e - (j - q[i].s) * q[i].l));

        //恰好装满，需要遍历一次dp数组找出最大值
        int res = 0;
        for (int i = 1; i <= m; i++) res = max(res, f[i]);
        printf("Case #%d: %d\n", ++idx, res);
    }
    return 0;
}