Hihocoder 1039 : 字符消除

http://haiyangxu.github.io/posts/2015/2015-03-23-hihocoder1039-character-elimination.html

小Hi最近在玩一个字符消除游戏。给定一个只包含大写字母"ABC"的字符串s，消除过程是如下进行的：

1)如果s包含长度超过1的由相同字母组成的子串，那么这些子串会被同时消除，余下的子串拼成新的字符串。例如"ABCCBCCCAA"中"CC","CCC"和"AA"会被同时消除，余下"AB"和"B"拼成新的字符串"ABB"。

2)上述消除会反复一轮一轮进行，直到新的字符串不包含相邻的相同字符为止。例如”ABCCBCCCAA”经过一轮消除得到"ABB"，再经过一轮消除得到"A"

游戏中的每一关小Hi都会面对一个字符串s。在消除开始前小Hi有机会在s中任意位置(第一个字符之前、最后一个字符之后以及相邻两个字符之间)插入任意一个字符('A','B'或者'C')，得到字符串t。t经过一系列消除后，小Hi的得分是消除掉的字符的总数。

请帮助小Hi计算要如何插入字符，才能获得最高得分。

基本思路是模拟消除，先写一个reduce函数出来进行字符串消除；然后在每一个字符直接分别插入 A B C，进行消除。

http://www.cnblogs.com/nowandforever/p/4415647.html

char in[3]={'A','B','C'};
 7 string getstring(string str)
 8 {
 9     int l=str.length();
10     if(l<=1) return str; //这里需要注意
11     string ss="";
12     for(int i=0;i<l-1;i++)
13     {
14         if(str[i]==str[i+1])
15         {
16             while(i+1<l&&str[i]==str[i+1]) i++;
17         }
18         else ss+=str[i];
19     }
20     if(str[l-1]!=str[l-2]) ss+=str[l-1];
21     return ss;
22 }
23 int main()
24 {
25     //freopen("a.txt","r",stdin);
26     int t,max;
27     string s;
28     cin>>t;
29     while(t--)
30     {
31         cin>>s;
32         max=0;
33         for(int i=0;i<s.length()-1;i++)
34         {
35             for(int j=0;j<3;j++)  //两重循环枚举。
36             {
37                 string str=s.substr(0,i+1)+in[j]+s.substr(i+1);
38                 int len=str.length();
39                 str=getstring(str);
40                 while(len>str.length())
41                 {
42                     len=str.length();
43                     str=getstring(str);
44                 }
45                 if(s.length()-len+1>max)  max=s.length()-len+1;
46             }
47         }
48         cout<<max<<endl;
49     }
50     return 0;
51 }

http://winterfell30.com/2015/07/05/hiho1039/