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;  
}