東京工業大学プログラミングコンテスト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; }