FLT

原题链接

题意

有一个敌人，血量为 \(h\)，你有两把武器，伤害和冷却时间分别为 \(p_i,t_i,i=\{1,2\}\)。当武器可用时（冷却完成），你可以使用一把，或者两把一起使用（当两个都冷却好）。

每次可以造成伤害 \(p-s\)，其中 \(s\) 是一个给定的值，\(p\) 是使用的武器的伤害总和。

问至少多少时间，可以消灭敌人（使其血量小于等于0）。

⭐rating: 2400

---

分析

定义 \(dp[i]\) 为造成的伤害为 \(i\)，所需要的最少时间。

• 一般转移情况：每次只由一个武器造成伤害。对于第一把武器，\(f[p_1]=t_1\)，那么 \(f[0-p_1]\) 都要更新成 \(t_1\)，因此需要对 \(0\) 取 \(\max\)。转移方程为 \(dp[i]=\min(dp[\max(0,i-(p_1-s))]+t_1,dp[\max(0,i-(p_2-s))]+t_2)\)。
• 复杂转移情况：枚举两个武器在最后一起对敌人造成伤害。对于第一个武器，假设第 \(j\) 次攻击的时候，第二个武器也冷却完成准备攻击。那么总的时间为 \(j\times t_1=T\)，第二个武器的使用次数为 \(T\div t_2\)。考虑造成的伤害 \(dmg\)，第一个武器独立攻击造成的伤害为 \((j-1)\times(p_1-s)\)，第二个武器独立攻击造成的伤害为 \((T-t_2)\div t_2\times(p_2-s)\)，两把武器共同攻击造成的伤害为 \(p_1+p_2-s\)。因此 \(dmg=(j-1)\times(p_1-s)+(T-t_2)\div t_2\times(p_2-s)+(p_1+p_2-s)\)。状态转移方程为 \(dp[i]=\min(dp[i],dp[\max(0,i-dmg)]+j\times t1)\)。对于第二把武器攻击 \(j\) 次同理。

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

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 5010;

LL dp[N];

int main() {
    LL p1, t1, p2, t2, h, s;
    cin >> p1 >> t1 >> p2 >> t2 >> h >> s;

    memset(dp, 0x3f, sizeof dp);
    dp[0] = 0;

    for (int i = 1; i <= h; i++) {
        dp[i] = min(dp[max(0ll, i - (p1 - s))] + t1, dp[max(0ll, i - (p2 - s))] + t2);
        for (int j = 1; j <= i; j++) {
            if (t1 * j >= t2) {
                LL dmg = (j - 1) * (p1 - s) + (j * t1 - t2) / t2 * (p2 - s) + (p1 + p2 - s);
                dp[i] = min(dp[i], dp[max(0ll, i - dmg)] + t1 * j);
            }
            if (t2 * j >= t1) {
                LL dmg = (j - 1) * (p2 - s) + (j * t2 - t1) / t1 * (p1 - s) + (p1 + p2 - s);
                dp[i] = min(dp[i], dp[max(0ll, i - dmg)] + t2 * j);
            }
        }
    }

    cout << dp[h] << endl;

    return 0;
}