String Deletion
题意
每次你可以从这个 01 字符串中删除一个字符 ，然后如果字符串不为空，系统则删除由相同字符组成的最大长度前缀 问最大操作数是多少
思路
有两种情况
1.当前字符串由相同字符组成的前缀长度大于1 那么肯定选择删除前缀中的一个字符比较好 因为如果选择删除后面的字符 那么前缀接下来肯定也要被系统删除
2.如果当前字符串由相同字符组成的前缀长度为1，那么就往后找是否存在连续的串，如果有的话就删除串中的一个字符，因为这样的话一个字符相同的串，可以被分为几次删除，否则当其为前缀时，系统一次就删除完了。另外 当找连续的串时，优先找位置靠前的，这样，在其被系统删除前，可以被最大化利用，从而我们坚持的回合数更多
代码
#include<bits/stdc++.h> #define INF 0x3f3f3f3f3f3f3f3f #define mod 1000000007 #define endl '\n' using namespace std; typedef long long LL; inline LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; } const int N = 200010; int n; char s[N]; void solve() { cin >> n; cin >> s; vector<int>v; int cnt = 0; int las = s[0]; for (int i = 0; i <= n; ++i) { if (s[i] == las)cnt++; else { v.push_back(cnt); las = s[i]; cnt = 1; } } int l = 0, r = 0, res = 0; n = v.size(); while (l <= r && r < n) { if (v[l] > 1) l++; //都选前缀 else { //从后面找一个连续的 while (r < n) { if (v[r] == 1) r++; else break; } if (r < n) v[r]--; //从后面自己拿走一个 else r--, l++; //只能从前面拿走 l++; } res++; while (r < l)r++; } printf("%d\n", res); } int main() { int t; cin >> t; while(t--) solve(); return 0; }
