ABC155 E - Payment

解いた問題を忘れているので思い出そうキャンペーン

問題のリンク

E - Payment

思考過程

・めっちゃ桁DPしたい制約。
・とりあえず、Nの桁数より2桁多い金額を支払うのは無駄。
・桁ごとに払う金額と紙幣の枚数を決めていきたい。繰り下がりを考えないといけない。

実験

・一番簡単な場合、N = 123に対して654を支払うような、繰り下がりの無い場合を考えてみる。この場合は6+5+4 = 15 枚使って払い、654 - 123 = 531 で、5+3+1 枚返ってくる。
→これを桁ごとに見ていくと、N[0] = 1に対して6を払うので、返ってくる枚数は6 - 1 = 5、よって使用された紙幣の枚数は6 + 5 = 11、、、
・繰り下がりがある場合、N = 123 に対して517 を払ってみる。517 - 123 = 394。
→N[0] = 1 に対し5 を払うので、返ってくる枚数は5 - 1 = 4としたいところだが、繰り下がりがあるので返ってくる枚数は3になる。
→N[1] = 2 に対し1 を払うとき、繰り下がりが発生し、11 - 2 = 9返ってくる。このとき、N[0]に繰り下がりの影響が伝搬する。

・繰り下がりの影響は下の桁から伝搬してくるので、下から見た方が良さげ。
・これらのことを考えると、dp table はdp[i][j][f] := 下からi桁目（1-indexed）まで見て、払う金額のi桁目をjとして状態f の時の払う紙幣の枚数の最小値。とする。状態fは1 := 繰り下がりがある、0 := 繰り下がりが無い。
・遷移は、(i, j, f) として、　　

・ここで、遷移前のjは遷移に使っていないので、省略できる。
以下実装

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; }
int main()
{
  string s; cin >> s;
  reverse(s.begin(), s.end());
  s.push_back('0');
  int n = s.size();
  
  int inf = 1e+9;
  int dp[1000010][2];
  rep(i,n+1) rep(j,2) dp[i][j] = inf;
  dp[0][0] = 0;
  
  rep(i,n+1) {
    int x = s[i] - '0';
    rep(j,2) {
      rep(d,10) {
    if(d > x) { // i+1桁目にs[i]より真に大きい数字を選ぶ場合
      chmin(dp[i+1][0], dp[i][j] + 2*d - x + (j ? -1 : 0) );
    }
    else if(d < x) {
      chmin(dp[i+1][1], dp[i][j] + 2*d - x + (j ? 9 : 10) );
    }
    else {
      chmin(dp[i+1][j], dp[i][j] + 2*d - x + (j ? 9 : 0) );
    }
      }
    }
  }

  cout << dp[n][0] << "\n";
  
  
  return 0;
}