https://atcoder.jp/contests/abc155/submissions/14397627
- 四捨五入的な考え方で最善の枚数が得られそうで得られないので意外と難しい
- 支払い金額と繰り下がりをdpで全て全探索する
- 初期値は dp[0][0] = 0;
- 繰り返しは rep(i, 0, Size(N) - 1) rep(d, 0, 2) rep(pay, 0, 10)
- 更新は dp[i + 1][1] = min(dp[i + 1][1], dp[i][d] + pay + change);
- 出力は min(dp.back()[0], dp.back()[1] + 1);
四捨五入のような考え方でN[i]が6以上だったら１桁多く支払う、という感じの普通の処理で実現できそうだが、様々なテストケースを試すと意外と上手く行かない。そこで、支払い金額と繰り下がり全て全探索する動的計画法で処理する。
dp[i][d] := i-1桁目からの繰り下がりがdだったときのi桁目までに使う枚数、と定義する。dp[i+1][d] = min( dp[i+1][d], dp[i][d] + 支払い枚数 pay + お釣り枚数 charge ); のような更新で最善枚数が得られる。
支払い金額Nを下の桁から見ていき、pay[i] < N[i] のとき繰り下がりが必要なので、お釣りは charge = 10+pay[i]-d-N[i] となる。N[i] <= pay[i] のとき繰り下がりが不要なので、お釣りは charge = pay[i] - d - N[i] となる。最後の桁でも繰り下がりが発生するので先頭にダミー値 0 を入れておくと実装が楽になる。
また、1桁目pay[0]では繰り下がりが存在しないので初期化には注意する。値 0 で初期化するのは dp[0][0] だけにして、dpをminで処理することから dp[0][0] 以外は十分大きな値（Pow10(6)など）にしておく。
