[AtCoder] ABC 155 E – Payment

2020年2月21日2020年12月15日

問題

方針

\( 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 \) が加算されます。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    string N;
    cin >> N;
    int l = N.length();
    int k[l];
    for (int i = 0; i < l; i++) {
        k[i] = N[i] - '0';
    }
    int d[l][2]{};
    d[0][0] = k[0];
    d[0][1] = 11 - k[0];
    
    for (int i = 1; i < l; i++) {
        d[i][0] = min(d[i - 1][0] + k[i], d[i - 1][1] + k[i]);
        d[i][1] = min(d[i - 1][0] + 11 - k[i], d[i - 1][1] + 9 - k[i]);
    }
    cout << min(d[l - 1][0], d[l - 1][1]) << "\n";
    return 0;
}