AOJ 2156 Magic Slayer

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2156

問題概要

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;
        }
    }
}