https://atcoder.jp/contests/abc153/submissions/14123891
- 個数無制限ナップサックDPは一次元で処理できる（ただし、繰り返しは二重ループ）
- 配るDPで制約オーバーするときは貰うDPでも制約オーバーで実装する
- infはオーバーフローしない程度の値（例えば
とか）だと実装が楽
- 初期値は dp[0]=0;
- 繰り返しは each(i, e, nyaa) rep(j, 0, H + Pow10(4) + 1)
- 更新は if (0 <= j - e.first) dp[j] = min(dp[j], dp[j - e.first] + e.second);
- 出力は rep(j, H, H + Pow10(4) + 1) ans = min(ans, dp[j]);
素直に考えると最初のうちはコスパの高い魔法で攻撃して、後半は残りヘルスを考えて無駄のないように魔法を使うのが最善という気持ちになる。しかし、これを実装するのは無理なのでDPかなという気持ちになる。魔法回数に制限がないことから所謂個数無制限ナップサックDPになる。
図を見ると分かるが、個数無制限ナップサックDPはDP[i-1]を引き継ぐかDP[i][j-A[i]]の2択しか遷移しない。したがって、実装するときはDPを一次元テーブルにすることが出来る。この定石は暗記すると良いと思う。配るDPで考えると分かりやすいが、Hピッタリにすることができないテストケースが有り得るので、制約オーバーまでDP[i][j]の[j]を拡張しておく必要がある。具体的には[j]をまで拡張しておく必要がある。
一次元DPの特徴として、DPテーブルの更新が疎になりinfが多く残る上にHピッタリが存在しない可能性が高いので、出力は rep(j, H, H + Pow10(4) + 1) ans = min(ans, dp[j]); とする必要がある。貰うDPで実装する場合でも、配るDPと本質的に同値なので[j]を拡張する必要がある。
なお、効率は悪いが二次元DPで実装することも可能ではある。
