TTPC2015 pF - レシート ( 桁DP )

F: レシート - 東京工業大学プログラミングコンテスト2015 | AtCoder
A(1≤A≤10^100)円の商品に対し、X円でそれを購入することができる。買い物の金額A、支払額X、お釣り(X−A)の3つの整数について10進数表記にしたとき、3つの数字が揃う桁の数を最大にしたい。
この三つの数である桁が同じということは、以下二つの条件中一つを満たすことに成る
• 三つとも０でかつその前の桁が borrowしてない
• 三つとも９でかつその前の桁が borrowしている ( 9 - 9 = 9 が実際に 8 - 9 = 9となって成り立つ )
入力範囲が小さいので揃えられる最大の桁数を状態に組み込む。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100 + 2;
const int INF = 1e9;
#define rep( i, a ) for(int i = 0; i < (int)( a ); ++i)

string a;
bool can[MAXN][2][MAXN]; // pos, did last digit borrow, matched

void solve(){
    reverse( a.begin(), a.end() );
    can[0][0][0] = true;
    rep( i, a.size() ) rep( j, 2 ) rep( k, a.size() + 1 ){
        int x = a[ i ] - '0';
        rep( d, 10 ){
            int d_x = d - x - j;
            int borrow = 0;
            if( d_x < 0 ) d_x += 10, ++borrow;
            can[i + 1][borrow][k + ( d == d_x )] |= can[i][j][k];
        }
    }
    int ans = 0;
    rep( i, a.size() + 1 )
        if( can[ a.size() ][0][i] || can[ a.size() ][1][i] )
            ans = i;
    cout << ans << endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin >> a;
    solve();
    return 0;
}