今回Fの正答率低かったみたいね。
https://atcoder.jp/contests/abc155/tasks/abc155_e
問題
10の累乗の紙幣のみある通貨を考える。
N円を支払うとき、支払う紙幣の枚数とお釣りの紙幣の枚数の合計の最小値を求めよ。
解法
下の桁から見ていくことにする。
選択肢は二つあって、今10^dの位を見ているとき、
- その桁をぴったり払い切る
- 1つ上の貨幣(10^(d+1))を払い、お釣りをもらう
後者の場合、上の桁で(10^(d+1))円だけ余分に支払わなければならない。
それぞれのケースを考え下の桁からDPしていけばよい。
int N; string S; int dp[2][2020202]; void solve() { int i,j,k,l,r,x,y; string s; cin>>S; reverse(ALL(S)); S+=string(1000005,'0'); dp[0][0]=0; dp[1][0]=1<<30; FOR(i,1000005) { dp[0][i+1]=min(dp[0][i]+S[i]-'0',dp[1][i]+(S[i]-'0'+1)); dp[1][i+1]=min(dp[0][i]+10-(S[i]-'0'),dp[1][i]+10-(S[i]-'0'+1)); } cout<<dp[0][1000004]<<endl; }
まとめ
同じような問題過去に見てそうな気はする。