GCJ 2016 Qualification Round B: Revenge of the Pancakes
解法
ある区間について、その区間をすべて '-' あるいは '+' に出来るかどうかを考える。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; string turn(const string &S) { string T = S; int N = S.size(); for (int i = 0; i < N; ++i) { if (S[N - 1 - i] == '+') { T[i] = '-'; } else { T[i] = '+'; } } return T; } map<pair<string, char>, ll> dp; ll solve(string S, char c) { char d = c == '+' ? '-' : '+'; int N = S.size(); if (N == 0) return 0; if (S.back() == c) return solve(S.substr(0, N - 1), c); if (dp.count({S, c})) return dp[{S, c}]; ll ans = N; if (S[0] == d) ans = min(ans, 1 + solve(turn(S).substr(0, N - 1), c)); ans = min(ans, 1 + solve(S.substr(0, N - 1), d)); dp[{S, c}] = ans; return ans; } int main() { cin.tie(0); ios::sync_with_stdio(false); int T; cin >> T; for (int i = 0; i < T; ++i) { string S; cin >> S; cout << "Case #" << (i + 1) << ": "; ll ans = min(solve(S, '+'), solve(S, '-') + 1); cout << ans << endl; } }