消除字符串游戏，选择一个字母，则会消除和该字母相同且连续的一段，然后左右两边合拢，若左右两边字母相同则再次消除掉。直到合拢时两边字母不相同。

问这样连续消除的最大次数。

思路：

先把连续相同的字母当成一个字母，然后求最长回文串，

则答案就是(最长长度+1)/;2

[cpp] view plaincopy

1. #pragma comment(linker, "/STACK:1024000000,1024000000")  
2. #include <cstdio>  
3. #include <cstring>  
4. #include <iostream>  
5. using namespace std;  
6. const int MAXN = 110010;  
7. //字符串长度<MAXN  
8. char Ma[MAXN * 2];  
9. int Mp[MAXN * 2];  
10. int Manacher(char s[]) {  
11.     int l = 0, len = strlen(s);  
12.     Ma[l++] = ‘$‘;  
13.     Ma[l++] = ‘#‘;  
14.     for (int i = 0; i<len; i++)  {  
15.         Ma[l++] = s[i];  
16.         Ma[l++] = ‘#‘;  
17.     }  
18.     Ma[l] = 0;  
19.     int mx = 0, id = 0;  
20.     for (int i = 0; i<l; i++)  {  
21.         Mp[i] = mx>i ? min(Mp[2 * id - i], mx - i) : 1;  
22.         while (Ma[i + Mp[i]] == Ma[i - Mp[i]])Mp[i]++;  
23.         if (i + Mp[i]>mx)   {  
24.             mx = i + Mp[i];    id = i;  
25.         }  
26.     }  
27.     int ans = 0;  
28.     for (int i = 0; i<2 * len + 2; i++)  
29.         ans = max(ans, Mp[i] - 1);  
30.     return ans;  
31. }  
32. char d[100100], s[100100];  
33. int main(){  
34.     int T; cin>>T;  
35.     while (T--)  {  
36.         scanf("%s", d);  
37.         int top = 0;  
38.         s[0] = d[0];  
39.         for(int i = 1; d[i]; i++)  
40.             if(d[i]!=s[top])  
41.                 s[++top] = d[i];  
42.         s[++top] = 0;  
43.         printf("%d\n", (Manacher(s)+1)/2);  
44.     }  
45.     return 0;  
46. } 

UVA 12378 Ball Blasting Game Manacher裸题