UVa-10626 : Buying Coke
問題概要
8円のコーラをN(<150)本買いたい。1円玉をn_1(<500)枚、5円玉をn_5(<100)枚、10円玉をn_10(<50)枚持っている。1本ずつコーラを買う。おつりは最小枚数で支払われる。このとき、コインを自販機の口に入れる回数を最小化する問題。
解法
動的計画法。dp[i本買った][残り1円][残り5円][残り10円]=最小枚数とすると状態数が多くてTLEしそう。残り硬貨の枚数を全部覚えておく必要はなくて、2種類について枚数が分かれば残りの枚数は引き算で求められる。これで状態数が減って通るようになる。ただし残り5円の枚数は途中で初期値より増えることがありうるので注意。
