SRM555 Div2 Medium

555

DP[何桁目まで]

string m5(string a)
{
  string b = a;
  a = a + "00";
  b = "00" + b;
  reverse(a.begin(), a.end());
  reverse(b.begin(), b.end());
  vector<char> v;
  const int size = b.size();
  int c = 0;
  for (int i = 0; i < size; ++i) {
    int n = (a[i] == '1') + (b[i] == '1') + c;
    if (n == 0) {
      v.push_back('0');
      c = 0;
    } else if (n == 1) {
      v.push_back('1');
      c = 0;
    } else if (n == 2) {
      v.push_back('0');
      c = 1;
    } else if (n == 3) {
      v.push_back('1');
      c = 1;
    }
  }
  if (c) v.push_back('1');
  reverse(v.begin(), v.end());
  string ret;
  for (int i = 0; i < v.size(); ++i) {
    ret += v[i];
  }
  return ret;
}

bool match(string a, int base, string b)
{
  if (base + b.size() <= a.size()) {
    for (int i = 0; i < b.size(); ++i) {
      if (a[i + base] != b[i]) return false;
    }
    return true;
  }
  return false;
}

class CuttingBitString {
public:
  int getmin(string S)
  {
    vector<string> v;
    v.push_back("1");
    v.push_back("101");

    while (v.back().size() <= 50) {
      v.push_back(m5(v.back()));
    }

    const int inf = 1 << 28;
    const int N = S.size() + 1;
    int dp[N];
    fill(dp, dp + N, inf);
    dp[0] = 0;

    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < v.size(); ++j) {
        if (match(S, i, v[j])) {
          dp[i + v[j].size()] = min(dp[i + v[j].size()], dp[i] + 1);
        }
      }
    }

    int ret = dp[N - 1];
    return ret == inf ? -1 : ret;
  }
};