贪心(微扰) + dp

这道题还是比较难的,前置知识:

  1. 贪心的微扰(邻项交换)证法,例题:国王游戏耍杂技的牛
  2. 01背包

算法1:暴力\(O(T * n! * n)\)

可以\(dfs\)全排列枚举所有吃的方案,然后每次线性算能量取最大值即可。

算法2:贪心 + dp \(O(T * n * \sum_{i = 1}^{n}s_i)\)

贪心将问题转化

发现有可能存在最优解的某些宝石的贡献为\(0\),我们剔除了这些宝石。

假设最优解的能量石排列长度为\(k (1 <= k <= n)\) 因为去掉了那些没有贡献的宝石,位置为:

\(a_1, a_2, a_3...a_k\)

那么对于任意两个位置\(i = a_l, j = a_{l + 1} (1 <= l < k)\)

交换后两个宝石的贡献总和不会变得更大,即(假设之前的总时间为\(t\) ):

\(E_i - t * L_i + E_j - (t + S_i) * L_j >= E_j - t * L_j + E_i - (t + S_j) * L_i\)

整理后:

\(S_i * L_j <= S_j * L_i\)

我们可以把跟\(i\)有关的放到一边,调整一下:

\(\frac{S_i}{L_i} <= \frac{S_j}{L_j}\)

这样,我们只要以如上条件作为宝石间排序的条件,进行一次\(sort\)

那么最优解的坐标(新的坐标)一定满足:

\(a_i < a_2 < a_3 ... < a_k\)

由于排序后的数组具有传递性,即对于\(i < j\),都有

\(\frac{S_i}{L_i} <= \frac{S_j}{L_j}\)

所以可以证明交换任意两项的都不会得到更小的值。(具体证明略,太麻烦了qwq)

dp

那么,我们只要搞个\(01\)背包,\(S_i\)作为费用,\(max(0, E_i - (t - S_i) * L_i)\) 作为价值 (\(t\)为当前花费时长)。

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

状态转移方程:

\(f[t] = max(f[t], f[t - S_i] + max(0, E_i - (t - S_i) * L_i))\)

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

初始状态:\(f[0] = 0\),其余为负无穷

答案:\(max(f[i]) (1 <= i <= \sum_{i = 1}^{n}s_i)\)

参考代码

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 105, S = 10005;
int n;
int f[S];
struct Node{
    int s, e, l;
    bool operator < (const Node &x) const{
        return s * x.l < x.s * l;
    }
}a[N];
int main() {
    int T, cnt = 0; scanf("%d", &T);
    while(T--) {
        memset(f, 0xcf, sizeof f);
        scanf("%d", &n);
        int t = 0;
        for(int i = 1, s, e, l; i <= n; i++) {
            scanf("%d%d%d", &s, &e, &l);
            t += s; a[i] = (Node) { s, e, l };
        }
        sort(a + 1, a + 1 + n);
        f[0] = 0;
        for(int i = 1; i <= n; i++) {
            for(int j = t; j >= a[i].s; j--)
                f[j] = max(f[j], f[j - a[i].s] + max(0, a[i].e - (j - a[i].s) * a[i].l));
        }
        int res = 0;
        for(int i = 1; i <= t; i++) res = max(res, f[i]);
        printf("Case #%d: %d\n", ++cnt, res);
    }
    return 0;
}
01-19 03:46