mayoko’s diary

プロコンとかいろいろ。

東京工業大学プログラミングコンテスト2015 F - レシート

解法

桁 DP します。

dp[keta][kuriage] = (keta 目の桁において, 繰り上げが kuriage の時の, 揃えられる桁の最大値) とします。
A+B = X の X を求めようとするのでなく, B を求めていこうとすることで, この dp を更新します。

B の keta 目の桁を i とした時, X の keta 目の桁及び A の keta 目の桁の数字が一致すれば最大値を +1 にして更新していく感じです。

const int MAXN = 105;
int dp[MAXN][2]; // keta, kuriage

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string A;
    cin >> A;
    reverse(A.begin(), A.end());
    int n = A.size();
    memset(dp, -1, sizeof(dp));
    dp[0][0] = 0;
    for (int keta = 0; keta < n; keta++) {
        int num = A[keta]-'0';
        for (int d = 0; d < 2; d++) {
            if (dp[keta][d] == -1) continue;
            for (int i = 0; i < 10; i++) {
                int sum = num+i+d;
                int nd = sum/10;
                int digit = sum%10;
                if (i == digit && digit == num) {
                    dp[keta+1][nd] = max(dp[keta][d]+1, dp[keta+1][nd]);
                } else {
                    dp[keta+1][nd] = max(dp[keta][d], dp[keta+1][nd]);
                }
            }
        }
    }
    cout << max(dp[n][0], dp[n][1]) << endl;
    return 0;
}