【AtCoder】ABC 410 E - Battles in a Row | 緑コーダーが解くAtCoder

atcoder.jp

配点: 450 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 1077 / NoviSteps: 1Q

問題概要
制約
考察
実装例
コメント

問題概要

高橋君が $N$ 体のモンスターと順に戦うゲームで遊ぼうとしており、最初、高橋君の体力は $H$ 、魔力は $M$ である。

$i$ 番目に戦うモンスターに対して、高橋君は以下のどちらかの行動を選ぶことができる。

魔法を使わずに戦う。体力が $A_i$ 以上のときのみ選ぶことができ、体力が $A_i$ 減少しモンスターを倒す。
魔法を使って戦う。魔力が $B_i$ 以上のときのみ選ぶことができ、魔力が $B_i$ 減少しモンスターを倒す。

$N$ 体全てのモンスターを倒すか、高橋君が行動できなくなるとゲーム終了である。ゲーム終了までに最大で何体のモンスターを倒せるか求めよ。

制約

$1 \leq N, H, M \leq 3000$
$1 \leq A_i,B_i \leq 3000$
入力は全て整数。

考察

この問題は、動的計画法によって解くことができる。

以下のような DP テーブルを考えよう。

$\mathrm{dp}_{i, h} :=$ $i$ 番目までのモンスターを倒した時点で、合計消費体力が $h$ であるときの合計消費魔力の最小値

初期値は

$\mathrm{dp}_{0, 0} = 0$
他は $\infty$

とする。

$i$ 番目のモンスターについて、 $h = 0, 1, \dots, H$ の順に、以下のように遷移する(貰うDP) :

魔法を使わずに倒す場合 : このモンスターについては消費体力が $A_{i-1}$ 、消費魔力が $0$ なので、ここまでの消費魔力の合計は $\mathrm{dp}_{i-1, h - A_{i-1}}$ である。ただし、 $h \geq A_{i-1}$ のときしか選べない。
魔法を使って倒す場合 : このモンスターについては消費体力が $0$ 、消費魔力が $B_{i-1}$ なので、ここまでの消費魔力の合計は $\mathrm{dp}_{i-1, h} + B_{i-1}$ である。ただし、 $\mathrm{dp}_{i-1, h} \neq \infty$ のときしか選べない。

この2パターンの最小値を採用する。つまり、

$\mathrm{dp}_{i, h} = \min(\mathrm{dp}_{i-1, h - A_{i-1}}, \mathrm{dp}_{i-1, h} + B_{i-1})$

である。ただし、計算後に $\mathrm{dp}_{i, h} \gt M$ となったときは実現不可能なので $\infty$ とする。

その後、 $\mathrm{dp}_{i, h} \neq \infty$ であるような $h \: (0 \leq h \leq H)$ が存在しなければ、モンスター $i$ は倒せなかったということなので、その時点で終了する。

空間計算量、時間計算量ともに $O(NH)$ となる。

実装例

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

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
#define repe(i, start, end) for (auto i = (start); (i) <= (end); (i)++)

constexpr int INF = 1e+9;

// ======================================== //

int main()
{
    int N, H, M;
    cin >> N >> H >> M;
    vector<int> A(N), B(N);
    rep(i, 0, N) cin >> A[i] >> B[i];

    vector<vector<int>> dp(N + 1, vector<int>(H + 1, INF));
    dp[0][0] = 0;
    int ans = 0;

    repe(i, 1, N)
    {
        repe(h, 0, H)
        {
            int cost_1 = (h >= A[i - 1]) ? dp[i - 1][h - A[i - 1]] : INF;
            int cost_2 = (dp[i - 1][h] != INF) ? dp[i - 1][h] + B[i - 1] : INF;

            dp[i][h] = min(cost_1, cost_2);

            if (dp[i][h] > M)
                dp[i][h] = INF;
        }

        bool flag = false;
        repe(h, 0, H)
        {
            if (dp[i][h] != INF)
                flag = true;
        }

        if (flag)
            ans++;
        else
            break;
    }

    cout << ans << endl;

    return 0;
}