けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 153 E - Crested Ibis vs Monster (緑色, 500 点)

個数制限なしナップサック!!!!!!!

問題へのリンク

問題概要

 N 種類の魔法を駆使して、HP が  H のモンスターを倒したい。

  •  i 番目の魔法は、魔力を  B_{i} だけ消費して、モンスターの HP を  A_{i} だけ減らすことができる

モンスターの HP を 0 以下にするのに消費する魔力の最小値を求めよ。

制約

  •  1 \le N \le 10^{3}
  •  1 \le H \le 10^{4}

解法 (1)

これは個数制限なしナップサック問題そのもの!!!!!
普通のナップサックは、容量  W 以内で、価値を最大化する問題だけど、今回は魔法によってモンスターに与えるダメージが  H 以上になる範囲で、魔力を最小化する問題。

実質はほとんど一緒になります。個数制限なしナップサックは、以前これらの記事に書いてみました!!!

qiita.com

今回の DP をざっくり書くと、

  • dp[ i ][ h ] := 最初の i 種類の魔法でモンスターに h のダメージを与える場合の、消費魔力の最小値

とする。このとき dp[ i ] から dp[ i + 1 ] への遷移は次のように詰めることができる。計算量は  O(NH) となる。

i 種類目の魔法を使わないとき

  • chmin(dp[ i + 1 ][ j ], dp[ i ][ j ]);

i 種類目の魔法を使うとき

dp[ i + 1 ][ j + A[ i ] ] について、i 種類目の魔法を 1 回使うことにした状態は、dp[ i + 1 ][ j ] と表せるので、

  • chmin(dp[ i + 1 ][ min( j + A[ i ], H) ], dp[ i + 1 ][ j ] + B[ i ])
#include <iostream>
#include <vector>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL<<60;

int main() {
    int H, N;
    cin >> H >> N;
    vector<int> A(N), B(N);
    for (int i = 0; i < N; ++i) cin >> A[i] >> B[i];
    
    vector<vector<long long>> dp(N+1, vector<long long>(H+1, INF));
    dp[0][0] = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j <= H; ++j) {
            chmin(dp[i+1][j], dp[i][j]);
            chmin(dp[i+1][min(j+A[i], H)], dp[i+1][j] + B[i]);
        }
    }
    cout << dp[N][H] << endl;
}

解法 (2):一次元にする

ナップサック問題は、導入説明ではわかりやすさのために二次元 DP で解説されることが多いが、一次元配列で実現することもできる!

そのようなテクニックについては、ここに特集してみました!

qiita.com

今回のを一次元にすると、こんな風に書けます!

#include <iostream>
#include <vector>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL<<60;

int main() {
    int H, N;
    cin >> H >> N;
    vector<int> A(N), B(N);
    for (int i = 0; i < N; ++i) cin >> A[i] >> B[i];
    
    vector<long long> dp(H+1, INF);
    dp[0] = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j <= H; ++j) {
            chmin(dp[min(j+A[i], H)], dp[j] + B[i]);
        }
    }
    cout << dp[H] << endl;
}