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;
  }
}