読者です 読者をやめる 読者になる 読者になる

AOJ 2156 Magic Slayer

問題概要

N 体のモンスターがいる.それぞれの体力は HP_i である.
自分が使える単体魔法と全体魔法がM個与えられる.それぞれの魔法には消費MPとダメージ量が決まっている.
この時,敵を全滅させるのに必要な最小のMPを求めよ.

・制約
1 <= N <= 100
1 <= HP_i <= 10^5
1 <= M <= 100
0 <= MP_j <= 99
0 <= damage_j <= 999999

解法

典型DP.この問題は実質ドラクエの「まんたん」と同じ.
まず,単体魔法しか無い場合は,それぞれの敵に対して個別にDPすればいいというのはすぐ分かる.
最終的に単体魔法だけ考えればいいことにできれば楽.なので,先に全体魔法によってあるダメージを与えるときに必要な最小のMPを求めておく.
cost[0][i] := 単体魔法だけ用いたときに,i 以上のダメージを与えるために必要な最小のMP.
cost[1][i] := 全体魔法だけ用いたときに,ちょうど i のダメージを与えるために必要な最小のMP.
これらを前計算しておけば,「ちょうど i だけ全体魔法でダメージを与えたときに,全滅させるのに必要な最小MP」は,「全体の体力から i だけ引いた後,単体魔法だけで全滅させるのに必要な最小MP」となるので,ここまでくればあとはやるだけ.
計算量は O((N+M)HP).

全部が全体(ないし単体)魔法のケース(1WA食らった.if で対処)や,単体魔法はあるけど全てダメージ0の場合(1WA食らった.ダメージ0の魔法をあらかじめ取り除くことで対処)などのコーナーケースに注意しよう.

ソースコード

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
using P = pair<int, int>;

constexpr int INF = 1e9;

int main() {
    int N;
    while(cin >> N, N) {
        vector<int> hp(N);
        int max_hp = 0;
        for(int i=0; i<N; ++i) {
            cin >> hp[i];
            max_hp = max(max_hp, hp[i]);
        }
        int M;
        cin >> M;
        vector<vector<P>> s(2);
        for(int i=0; i<M; ++i) {
            string name, target;
            int mp, dam;
            cin >> name >> mp >> target >> dam;
            if(dam == 0) {
                continue;
            }
            s[target == "All"].emplace_back(mp, dam);
        }
        vector<vector<int>> cost(2, vector<int>(max_hp+1, INF));
        cost[0][0] = cost[1][0] = 0;
        for(int k=0; k<2; ++k) {
            for(int i=0; i<s[k].size(); ++i) {
                for(int j=0; j<=max_hp; ++j) {
                    int t = min(max_hp, j+s[k][i].second);
                    cost[k][t] = min(cost[k][t], cost[k][j] + s[k][i].first);
                }
            }
        }
        for(int j=max_hp; j>=1; --j) {
            cost[0][j-1] = min(cost[0][j-1], cost[0][j]);
        }
        if(s[0].size() == 0) {
            cout << cost[1][max_hp] << endl;
        } else {
            int res = INF;
            for(int i=0; i<=max_hp; ++i) {
                if(cost[1][i] == INF) {
                    continue;
                }
                int t = cost[1][i];
                for(int j=0; j<N; ++j) {
                    int rest_hp = hp[j] - i;
                    if(rest_hp <= 0 || cost[0][rest_hp] == INF) {
                        continue;
                    }
                    t += cost[0][rest_hp];
                }
                res = min(res, t);
            }
            cout << res << endl;
        }
    }
}