题目链接: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;
}