SRM665 Div1 Easy "LuckySum"
解法
以下、参考にさせていただきました。m(_ _)m
kmjp.hatenablog.jp
事後
実装がちょっと難しくなると頭が混乱するのなんとかして
ソースコード
const long long INF = 123456789012345LL; long long dp[20][2][3]; int sums[20]; class LuckySum { public: long long construct(string note) { int n = note.size(); // sums初期化 for (int i = 0; i < n; i++) sums[n - i - 1] = note[i] == '?' ? -1 : note[i] - '0'; // dp初期化 for (int d = 0; d <= n; d++) for (int c = 0; c < 2; c++) for (int e = 0; e < 3; e++) dp[d][c][e] = INF; dp[0][0][0] = 0; // dp更新 int ds[] = {7, 4, 0}; long long p_10 = 1; for (int d = 0; d < n; d++) { for (int c = 0; c < 2; c++) for (int e = 0; e < 3; e++) { if (dp[d][c][e] == INF) continue; for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) { int a = ds[i]; int b = ds[j]; int s = a + b + c; int dight = s % 10; int carry = s / 10; int end = (a == 0 ? 1 : 0) + (b == 0 ? 1 : 0); // 未完了のlackyNumberの数より使用するLackyNumberの数の方が多ければやらない if (2 - e < 2 - end) continue; // 最初の桁であり、endが1以上であればやらない if (d == 0 && end >= 1) continue; // sumsと合っていなければやらない if (sums[d] != -1 && sums[d] != dight) continue; // endが2であり、最後の桁でない、または繰り上がりがなければやらない if (end == 2 && (d != n - 1 || c == 0)) continue; dp[d + 1][carry][end] = min(dp[d + 1][carry][end], dp[d][c][e] + dight * p_10); } } p_10 *= 10; } // dp答え long long ans = INF; for (int e = 0; e < 3; e++) { ans = min(ans, dp[n][0][e]); } return ans == INF ? -1 : ans; } };