hihoCoder 1039-字符消除 #1039 : 字符消除 时间限制:1000ms 单点时限:1000ms 内存限制:256MB 描述 小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计算要如何插入字符，才能获得最高得分。 输入 输入第一行是一个整数T(1<=T<=100)，代表测试数据的数量。 之后T行每行一个由’A”B”C’组成的字符串s，长度不超过100。 输出 对于每一行输入的字符串，输出小Hi最高能得到的分数。 提示 第一组数据：在”ABCBCCCAA”的第2个字符后插入’C’得到”ABCCBCCCAA”，消除后得到”A”，总共消除9个字符(包括插入的’C’)。 第二组数据：”AAA”插入’A’得到”AAAA”，消除后得到””，总共消除4个字符。 第三组数据：无论是插入字符后得到”AABC”,”ABBC”还是”ABCC”都最多消除2个字符。 样例输入 3 ABCBCCCAA AAA ABC 样例输出 9 4 2

---

这个题目要稍微思考一下，当然很容易想到穷举测试，但我在边写代码的时候还是在担心穷举会不会超时什么的。后来结果还不错。 总体思路就是在字符串的所有可以插空的位置分别插入A、B、C看能消除多少个字符，然后求最大值。所以这里关键就是怎样求一个字符串最终能消除多少个字符。 题目给出的消除策略是这样的：

1)如果s包含长度超过1的由相同字母组成的子串，那么这些子串会被同时消除，余下的子串拼成新的字符串。 2)上述消除会反复一轮一轮进行，直到新的字符串不包含相邻的相同字符为止。

一定要注意，相同的子串同时消除。我一开始想用堆栈来做，来一个字符，判断是否和栈顶相同，如果相同，则消除，并统计消除个数。但是这样会有问题，比如字符串ABCCBCCCAA，如果用堆栈来做的话：进A，进B，进C,C，消除C,C，进B，消除B,B，进C,C,C，消除C,C,C，进A,A，消除A,A,A，这样所有字符都消除了。但是按原题的思路，所有相同的子串同时消除，第一轮同时只能消除C,C，C,C,C，A,A，得到ABB，然后消除B,B，最终剩A。所以用堆栈不行。 后来是这样解决的，只需遍历一遍字符串，如果s[i]==s[i+1]则说明出现重复子串了，令j=i+1，然后一个while(s[i]==s[j])循环计数。如果可以消除，则递归调用该函数继续消除，否则直接返回。 代码如下： [cpp] #include <iostream> #include<string> using namespace std; //递归求解一个字符串最多能消除多少个字符 int get_erase_num(string s,int rs) { int G[100]={0};//用来记录整个字符串能够消除的字符的位置 int s_size=s.size(); bool is_done=true;//是否检查结束的标识 for(int i=0;i<s_size-1;i++)//注意上限s_size-1 { if(s[i]==s[i+1])//然后判断是否有至少两个连续的字符出现 { G[i]=1; is_done=false; rs++; int j=i+1; while(s[i]==s[j]) { G[j]=1; rs++; j++; if(j>=s_size)//检查是否超限 { break; } } i=j-1; } } if(!is_done)//如果可以消除，则还没有结束 { string ss=""; for(int i=0;i<s_size;i++) { if(G[i]==0) ss+=s[i];//同时消除重复子串后的结果串 } return get_erase_num(ss,rs);//递归 } return rs;//结束返回 } int main() { int n; string s; cin>>n; while(n–) { cin>>s; int s_size=s.size(); int max_m=-1; //在所有可以插入的位置依次分别测试插入A,B,C的结果 for(int i=0;i<s_size+1;i++) { if(i==s_size)//如果要在字符串的末尾插入字符 { int A_result=get_erase_num(s+"A",0); if(A_result>max_m) max_m=A_result; int B_result=get_erase_num(s+"B",0); if(B_result>max_m) max_m=B_result; int C_result=get_erase_num(s+"C",0); if(C_result>max_m) max_m=C_result; } else//插入位置除了末尾 { int A_result=get_erase_num(s.substr(0,i)+"A"+s.substr(i),0); if(A_result>max_m) max_m=A_result; int B_result=get_erase_num(s.substr(0,i)+"B"+s.substr(i),0); if(B_result>max_m) max_m=B_result; int C_result=get_erase_num(s.substr(0,i)+"C"+s.substr(i),0); if(C_result>max_m) max_m=C_result; } } cout<<max_m<<endl; } return 0; } [/cpp] 该代码提交结果AC，运行用时45ms，内存0MB，还不错。]]>