hihoCoder 1039字符消除（字符串处理）暴力

秒速五厘米 2024-02-18 19:10 98阅读 0赞

#### \#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'，对消除的字符用'\*'代替，while循环进行一遍又一遍的消除，直到某次消除个数为0，退出while循环。

AC代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn = 100 + 5;
    char s[maxn];
    char b[maxn];
    
    int main(){
    	int T;
    	scanf("%d",&T);
    	while(T--){
    		scanf("%s",s);
    		int total = 0;
    		
    		for(int i = 0; i < 3; i++){
    			char ch = 'A' + i;
    			for(int j = 0; j < strlen(s); j++){  //插入位置 
    				int cnt = 0;
    				
    				for(int k = 0; k < strlen(s); k++){  //插入字符后的新字符串 
    					if(cnt == j) {
    						b[cnt++] = ch;
    						k--;
    					}
    					else b[cnt++] = s[k];
    				}
    				b[cnt]='\0';
    				//printf("%s-----",b);
    				
    				
    				int sum = 0;  //当前字符串消除字符数量 
    				int fg = 1;  //用于退出while 
    				while(fg){
    					cnt = 0;
    					int flag = 0;  //判断是否连续多个相同字符 
    					for(int k = 0; k < strlen(b); k++){
    						if(b[k] == '*') continue;
    						int tmp = k;
    						while(b[k+1] == '*')k++;
                  
                        if(b[tmp] == b[k+1]){  //判断"前" "后"字符关系（不一定相邻，中间隔了*,*表示删除元素） 
                           flag = 1;
    					   b[tmp] = '*';	
    					   cnt++;
    					  } else if(flag){
    					  	flag = 0;
    					  	b[tmp]='*';
    					  	cnt++;
    					  } 		  
    					      
    					}	
    					sum += cnt;
    					if(cnt==0) fg=0;   //如果本次没有消除一个元素，则表示消除完毕 
    				}
    				
    				total = max(total,sum);
    				//printf("%d %s\n",total,b);
    			}
    		}
    		
    		printf("%d\n",total);
    	}
    	return 0;
    }
    
    
    // 测试数据：ACAAA  -> 输出6：ACAACA