CF1862F Magic Will Save the World

这道题目要求使用两种魔法（水魔法和火魔法）消灭一组怪物，每个怪物有不同的强度，而魔法的获得速度也不同。通过贪心策略，将尽可能多的水魔法用于消灭怪物，并使用 01 背包预处理得到最大水魔力消耗，然后判断剩余怪物是否能够被火魔法消灭，最终输出最少需要的时间。

题目大意

你有两个魔法，水魔法和火魔法。每秒你分别能获得 $s,f$ 点对应的魔力。现在有 $n$ 个怪物，每个怪物的强度为 $s_i$。强度为 $s_i$ 的怪物需要 $s_i$ 点魔力的任意魔法消灭。施法不耗任何时间，请问最少几秒后可以杀完全部的怪物？

思路

显然放到最后一起杀更方便处理，问题转变成判断 $curr_s,curr_f$ 的水魔法和火魔法能不能杀光全部的怪物。消灭怪物所需的能量总和 $sum_s$ 是固定的，贪心的考虑，我们需要让 $curr_s$ 的水魔法尽可能的使用得更多去消灭怪兽（这个操作可以用 01 背包预处理好），然后判断剩下的怪兽能不能被火能量消灭。

一开始写了一个裸的二维 01 背包，不出意外的 MLE 了，之后优化成一维背包竟然一发就过了。

代码

int w, f, n, sum_s, cnt, s[110],
    dp[1000010]; // dp[i][j]表示用j个水打前i个，最多能用掉多少水
void solve() {
    sum_s = cnt = 0;
    cin >> w >> f >> n;
    rep(i, 1, n) {
        cin >> s[i];
        sum_s += s[i];
    }
    rep(j, 1, sum_s) dp[j] = 0;
    rep(i, 1, n) {
        per(j, sum_s, 1) {
            if (j >= s[i])
                dp[j] = max(dp[j], dp[j - s[i]] + s[i]);
        }
    }
    int curr_w = 0, curr_f = 0;
    while (++cnt) {
        curr_w += w, curr_f += f;
        if (curr_f >= sum_s - dp[min(curr_w, sum_s)]) {
            break;
        }
    }
    cout << cnt << endl;
}