ABC155 E. Payment

問題

AtCoder王国では、価値が1,10,100,1000,...,10^(10^100)の紙幣になっている。
今、商品の価値がNであるような商品を買いたい。
各紙幣は十分な枚数を持っているとした場合、この商品を買うために払う枚数とおつりの枚数を適切に最小化した場合、最小で何枚にすることができるか？

制約

• 1 <= N <= 10^1000000

解法

各桁に注目すると、ある桁での数字N_iをそのまま払う場合は、「払う枚数はN_i枚、お釣りは0枚」で、もしそれよりも大きい価値の紙幣で払う場合は、「払う枚数は1枚、お釣りは(この桁については)10-N_i枚」になる。

したがって、各桁について、そのまま払うか？、より価値の高い紙幣で払うか？の選択が考えられるため、これをdpで求める。

dp[i][j] := i番目の桁で、j=1なら一つ前の桁で高い紙幣で払うことにした、j=0ならしなかった場合の、最小やり取り枚数

遷移は、もらうDPで考えると、i+1番目の桁では、

• dp[i][0]から、そのまま払う+N_iか、高い紙幣で払う+(10-N_i)か
• dp[i][1]から、そのまま払う+(N_i+1)か、高い紙幣で払う+(10-(N_i+1))か

の4種類で、

int n = N[i]-'0';
dp[i+1][0] = min(dp[i+1][0], dp[i][0] + n);
dp[i+1][1] = min(dp[i+1][1], dp[i][0] + (10-n));
dp[i+1][0] = min(dp[i+1][0], dp[i][1] + (n+1));
dp[i+1][1] = min(dp[i+1][1], dp[i][1] + (10-(n+1)));

のような感じになる。
(Nにleading-zeroをつけて計算しておくと、最上位付近の桁での計算を木にしなくて良くなる)