HDU 4950 Monster：判斷能否擊殺怪物的數學條件分析

題目重述

怪物初始血量 h。每回合玩家攻擊減 a，回合結束怪物回血 b。連續 k 回合攻擊後必須休息 1 回合（不攻擊、怪物仍回血）。可提前休息。問能否將怪物血量降至 < 1。

核心觀察

每個 k+1 回合為一個大週期（k 攻擊 + 1 休息）。大週期內怪物淨掉血：k*a - (k+1)*b。若淨掉血 ≤ 0，則隨著時間怪物血量不減反增，唯一機會在前 k 回合內直接打死。

判斷條件

玩家獲勝 當且僅當 以下任一成立：

1. a >= h：首回合直接秒殺。
2. k*a - (k+1)*b > 0：大週期淨掉血為正，最終必死。
3. (k-1)*a - k*b + a >= h：即前 k 回合攻擊 + 第 k+1 回合休息前的累計傷害 ≥ h（不需進入下一大週期）。

C++ 代碼

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int64 h, a, b, k;
    int tc = 0;
    while (cin >> h >> a >> b >> k, h || a || b || k) {
        bool win = (a >= h) ||
                   (a - b) * k - b > 0 ||
                   (a - b) * (k - 1) + a >= h;
        cout << "Case #" << ++tc << ": " << (win ? "YES" : "NO") << '\n';
    }
    return 0;
}

複雜度

• 時間：O(1) 每測試用例。
• 空間：O(1)。