個数制限なしナップサック!!!!!!!
問題概要
種類の魔法を駆使して、HP が のモンスターを倒したい。
- 番目の魔法は、魔力を だけ消費して、モンスターの HP を だけ減らすことができる
モンスターの HP を 0 以下にするのに消費する魔力の最小値を求めよ。
制約
解法 (1)
これは個数制限なしナップサック問題そのもの!!!!!
普通のナップサックは、容量 以内で、価値を最大化する問題だけど、今回は魔法によってモンスターに与えるダメージが 以上になる範囲で、魔力を最小化する問題。
実質はほとんど一緒になります。個数制限なしナップサックは、以前これらの記事に書いてみました!!!
今回の DP をざっくり書くと、
- dp[ i ][ h ] := 最初の i 種類の魔法でモンスターに h のダメージを与える場合の、消費魔力の最小値
とする。このとき dp[ i ] から dp[ i + 1 ] への遷移は次のように詰めることができる。計算量は となる。
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 で解説されることが多いが、一次元配列で実現することもできる!
そのようなテクニックについては、ここに特集してみました!
今回のを一次元にすると、こんな風に書けます!
#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; }