[AtCoder] ABC 155 E – Payment

問題

方針

\( N \) を数値として扱うと制約が大きすぎるので、桁DPを行います。上位 \( i \) 桁目までの数字に対して、\( d(i, 0) \) を \( i \) 桁目の数字の分だけお札を使ったときの最小値とし、\( d(i, 1) \) を \( i + 1 \) 桁のお札で支払い、おつりを受け取るときの最小値とします。 ここで、\( N_i \) を 上位 \( i \) 桁目の数字とします。 初期値は、

\[
\begin{eqnarray}
d(0, 0) &=& N_0 \\
d(0, 1) &=& 11 – N_0
\end{eqnarray}
\]

です。更新式は、

\[
\begin{eqnarray}
d(i + 1, 0) &=& \min(d(i, 0) + N_{i + 1}, d(i, 1) + N_{i + 1}) \\
d(i + 1, 1) &=& \min(d(i, 0) + 11 – N_{i + 1}, d(i, 1) + 9 – N_{i + 1})
\end{eqnarray}
\]

となります。下の式で、\( d(i, 0) + 11 – N_{i + 1} \) では、\( i + 1 \) 桁目の数字に対して、新たに \( i + 2 \) 桁のお札で支払うので、おつりと合わせて \( 11 \) と加算されます。また、\( d(i, 1) + 9 – N_{i + 1}\) は、\( i + 2 \) 桁目で発生したおつりから \( i + 2 \) 桁のお札を \( 1 \) 枚借りてきて支払うので、\( 9 \) が加算されます。

コード