ABC155 E - Payment
36 を支払うときに価値1の紙幣を使う枚数は「6枚」か「0枚で価値10の紙幣1枚を支払ってお釣りで価値1を4枚もらう」の二択です.このように,各価値の紙幣を使う方法はぴったり同じ枚数を用いるか,一つ上の価値の紙幣を使ってお釣りをもらうかの二択です.
dp[下からi桁目][一つ下の貨幣の支払いで使ったか?] = 紙幣を用いる最小枚数 と状態を持ち,下の桁から参照するDPを行うことで数えることができます.
#include <bits/stdc++.h> using namespace std; using ll = long long; using PII = pair<ll, ll>; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() template<typename T> void chmin(T &a, const T &b) { a = min(a, b); } template<typename T> void chmax(T &a, const T &b) { a = max(a, b); } struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio; const ll INF = 1LL<<60; ll dp[1000001][2]; int main(void) { string s; cin >> s; ll n = s.size(); dp[n][1] = INF; for(ll i=n; i>=1; --i) { dp[i-1][0] = dp[i][0] + s[i-1]-'0'; chmin(dp[i-1][0], dp[i][1] + s[i-1]-'0'+1); dp[i-1][1] = dp[i][0] + 10-(s[i-1]-'0'); chmin(dp[i-1][1], dp[i][1] + 10-(s[i-1]-'0'+1)); } cout << min(dp[0][0], dp[0][1]+1) << endl; return 0; }