题解 CF1743E FTL

其实只进行一次连发的 $f_i$ 不用去 dp，直接二分一下就行，这样会运行得更快。

思路

我们容易注意到，每进行完一次连发之后，两个炮都要重新进入一轮冷却，相当于我们面对的是一个血量更少的敌人，这构成了一个新的子问题。我们只需要考虑在打掉怪物多少血量的时候连发，可以让总时间最小。这显然是一个 dp 问题，定义 $f_i$ 表示只能连发一次并且打掉 $i$ 的血量所需要的最小时间，$g_i$ 表示连发多次并且打掉 $i$ 的血量所需要的最小时间。容易得到 dp 方程如下 ：

$$ g_i = \min_{j < i}\lbrace g_j + f _{i - j}\rbrace $$

对于 $f_i$ 我们二分枚举所需时间，这样更方便一些。

但是有一种情况，一个炮冷却时间特别长，所以连发不如单个打划算。我们在二分的时候把这种情况考虑一下就行。

代码

#define int long long
const int inf = 0x3f3f3f3f3f3f3f3fll;
int p1, p2, t1, t2, h, s;
int f[10010], g[10010];
int chk(int x) {
    if (x < t1 || x < t2) return x / t1 * (p1 - s) + x / t2 * (p2 - s);
    int ret = 0;
    ret += p1 + p2 - s;
    int r1 = x - t1, r2 = x - t2;
    ret += r1 / t1 * (p1 - s) + r2 / t2 * (p2 - s);
    if (ret < 0) ret = inf;
    return ret;
}
void solve() {
    p1 = read(), t1 = read(), p2 = read(), t2 = read();
    h = read(), s = read();
    for (int i = 1; i <= h; i++) {
        int p = 0;
        for (int j = (1ll << 60); j; j >>= 1) 
            if (chk(p + j) < i) p += j;
        f[i] = p + 1;
    }
    memset(g, 0x3f, sizeof(g));
    g[0] = 0;
    for (int i = 1; i <= h; i++) 
        for (int j = 0; j < i; j++) 
            g[i] = min(g[i], g[j] + f[i - j]);
    cout << g[h] << endl;
}