問題概要 K個のポストがある。ポストを壊すのに爆弾が最低いくつ必要かをしりたい。最低爆弾をいくつ用意する必要があるか求める問題。 解法 状態を(残りポスト、下限、上限)としてDP。

問題概要 8円のコーラをN( 解法 動的計画法。dp[i本買った][残り1円][残り5円][残り10円]=最小枚数とすると状態数が多くてTLEしそう。残り硬貨の枚数を全部覚えておく必要はなくて、2種類について枚数が分かれば残りの枚数は引き算で求められる。これで状態…