题解 CF1743E 【ATL】

Leasier · 2022-10-19 18:39:39 · 题解

Update on 2022.10.26：感谢 T_E_IO。

Update on 2024.11.8：感谢 Ebola 和 w9095。

首先你可以不进行任何一次双炮连发。

现在假定我们要进行双炮连发，注意到每进行完一次就相当于回到了初始状态（即两个炮都未装上）。

考虑 dp，设 f_i 表示通过若干单发 + 最后恰好一次双炮连发使敌方耐久度减少 i 的最小时间，g_i 表示通过若干次若干单发 + 双炮连发的连续组合使敌方耐久度减少 i 的最小时间。

初值：f_0 = g_0 = 0。

转移：

• 对于 g_i：g_i = \displaystyle\min_{j = 0}^{i - 1} (g_j + f_{i - j})。

• 对于 f_i：考虑枚举连发前第一种炮弹发射了 j 发，其中 j \geq 0 且 j(p1 - s) + (p1 + p2 - s) \leq i，则第二种炮弹至少发射了 \lceil \frac{i - (j(p1 - s) + (p1 + p2 - s))}{p2 - s} \rceil 发，则此时我们令 f_i \leftarrow \min(f_i, \max(t_1(j + 1), t_2(\lceil \frac{i - (j(p1 - s) + (p1 + p2 - s))}{p2 - s} \rceil + 1))) 即可。

答案：\displaystyle\min_{i = h} g_i。

时间复杂度为 O(h^2)。

代码：

#include <stdio.h>

typedef long long ll;

ll dp1[10007], dp2[10007]; 

inline int max(int a, int b){
    return a > b ? a : b;
}

inline ll min(ll a, ll b){
    return a < b ? a : b;
}

inline ll max(ll a, ll b){
    return a > b ? a : b;
}

int main(){
    int p1, p2, h, s, n;
    ll t1, t2, ans;
    scanf("%d %lld", &p1, &t1);
    scanf("%d %lld", &p2, &t2);
    scanf("%d %d", &h, &s);
    n = h + max(p1, p2);
    ans = min(t1 * ((h - 1) / (p1 - s) + 1), t2 * ((h - 1) / (p2 - s) + 1));
    for (int i = 1; i <= n; i++){
        dp1[i] = dp2[i] = 4e18;
        for (int j = 0; j * (p1 - s) + (p1 + p2 - s) <= i; j++){
            ll x = i - (j * (p1 - s) + (p1 + p2 - s));
            dp1[i] = min(dp1[i], max(t1 * (j + 1), t2 * ((x == 0 ? 0 : (x - 1) / (p2 - s) + 1) + 1)));
        }
        for (int j = 0; j < i; j++){
            dp2[i] = min(dp2[i], dp2[j] + dp1[i - j]);
        }
        if (i >= h) ans = min(ans, dp2[i]);
    }
    printf("%lld", ans);
    return 0;
}