ZOJ 3983 -Crusaders Quest

题目链接：ZOJ-3983

记录连续字母块的首尾位置，暴力枚举删除位置，更新最大值。

code：

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int res;

void dfs(string s, int ans) {
  if (s.size() == 0) {
    res = max(ans, res);
    return;
  }
  vector<int> index;
  index.push_back(0);
  int j = 0;
  int i = 1;
  for (i = 1; s[i]; i++) {
    if (s[i] != s[j]) {
      index.push_back(i);
      j = i;
    }
  }
  index.push_back(i);
  vector<int>::iterator it = index.begin();
  string t=s;
  while ((it+1) != index.end()) {
    s.erase(s.begin() + *it, s.begin() + *(it + 1));
    if (*(it + 1) - *it == 3) {
      dfs(s, ans + 1);
    } else {
      dfs(s, ans);
    }
    ++it;
    s=t;
  }
}

int main() {
  int T;
  cin >> T;
  int kase = 0;
  while (T--) {
    string s;
    cin >> s;
    res = 0;
    dfs(s, 0);
    cout << res << endl;
  }
  return 0;
}