[AtCoder] ABC 153 E – Crested Ibis vs Monster

2020年1月27日2020年12月15日

問題

方針

商品を無数に選ぶことができるナップザック問題なので、動的計画法を使って解きます。\( d(i) \) をモンスターに \( i \) ダメージ与えれるために必要な魔力とします。初期値は、\( d(0) = 0 \) であり、\( d(i) = \infty \ (i \neq 0) \) とします。

更新式は、\( d(i + A_j) = \min(d(i + A_j), d(i) + B_j) \ (1\leq j \leq N)\) です。注意として、\( d(H) = \infty \) となることがあるので、\( d(i) \ (H \leq i) \) を満たす \( i \) について最小値を探します。

方針

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int H, N;
    cin >> H >> N;
    int A[N], B[N];
    for (int i = 0; i < N; i++) {
        cin >> A[i] >> B[i];
    }
    int l = 30000;
    ll INF = 10000000000;
    ll d[l];
    fill(d, d + l, INF);
    d[0] = 0;
    
    for (int i = 0; i < H; i++) {
        if (d[i] == INF) continue;
        for (int j = 0; j < N; j++) {
            d[i + A[j]] = min(d[i + A[j]], d[i] + B[j]);
        }
    }
    ll ans = INF;
    for (int i = H; i < l; i++) {
        ans = min(ans, d[i]);
    }
    cout << ans << "\n";
    return 0;
}