题目链接：http://hihocoder.com/problemset/problem/1039
题意：给定一个只由{A, B, C}组成的字符串s，长度为n, 故包含n+1个空隙；现要求在某个空隙插入一个来自{A, B, C}的字符，然后按照以下“消除规则”对插入后的字符串进行消除操作，问最多能消掉几个字符（包含插入的一个）。
消除规则：
1. 自左至右扫描当前字符串，若字符v从某个位置开始连续出现了2次及以上，则此区间内的v全部消除；
2. 重复步骤1直至不再有可消除的字符。
思路：模拟，枚举。
这个题有点像之前数据结构编程作业的“祖玛”一题，同样是会产生连锁反应的“消除规则”，不过那道题是给定一个方案，包含一连串的插入操作，直接用动态链表模拟就好。而这道题要求最佳方案，所以可以枚举所有可能的插入方案，对每个方案都要模拟出消除后的结果。动态申请内存显然不合适，而节点数又固定为n+1，所以我用静态链表来实现。
有两个值得注意的地方：
1. 之前以为可以这样剪枝：在挑选每个位置插入的字符时，只考虑和相邻字符相同的。然而一直WA。。。感谢这篇题解给出的反例 BBBAB http://blog.csdn.net/Lu597203933/article/details/44245411
2. 关于复杂度分析：开始时不敢枚举，总感觉是指数的复杂度，但听了Kirai同学的聚合分析后明白了。简述如下：
(1)首先有n+1个空隙，每个空隙有3种选择，故共有3*(n+1)种插入方案；
(2)其次对于每个插入方案，要经历若干趟扫描，而停止扫描的标志为上一趟扫描是否发生过消除；
具体地，设第 i 趟扫描前字符串长度为 m ，由于一趟扫描过程中指针不回溯，所以一趟扫描花费的时间为线性的，记为t[i] = T(m)。若此趟发生了消除，则字符串的长度必然至少减1，故t[i+1] <= T(m-1)。而初始字符串长度为n+1,故至多经过n趟扫描后，必然达到最终状态。
至此观察所有趟扫描的时间花费序列t，从t[n]到t[1]，呈算术级数，故求和后与末项平方同阶，为T(n2)。
(3)总的时间复杂度为O(n2 * 3 * (n+1)) = O(n3)
关于代码：Debug的时间太长了，需要多写些模拟题
1 #include <cstdio> 2 #include <cstring> 3 #include <string> 4 #include <algorithm> 5 #include <map> 6 #define REP(N) for(int i=0; i<(N); i++) 7 #define REPE(N) for(int i=1; i<=(N); i++) 8 #define CLEAR(A, X) memset(A, X, sizeof(A)) 9 #define FREAD(FN) freopen((FN), "r", stdin) 10 #define pb(a) push_back(a) 11 #define SINT(X) scanf("%d", &(X)) 12 using namespace std; 13 const int MAX_C = 105; 14 15 struct Node 16 { 17 char c; 18 int next; 19 }nodes[MAX_C];//静态链表 20 int n;//节点个数 21 int head; 22 23 int T; 24 char s[MAX_C]; 25 int ans; 26 27 void reset(){//重置为原始序列 28 n = 0; 29 for(int i = 0; s[i] != '\0'; i++){//[1, n] 30 nodes[i].next = i+1;//来自前驱的引用 31 nodes[i+1].c = s[i];//[0]为头结点 32 n++; 33 } 34 nodes[n].next = -1;//末元的后继 35 } 36 37 int main() 38 { 39 FREAD("1039.txt"); 40 head = 0; 41 SINT(T); 42 while(T--){ 43 scanf("%s", s); 44 ans = 0; 45 reset();//初始化原始序列 46 for(char t = 'A'; t <= 'C'; t++){ 47 nodes[n+1].c = t;//待插入的元素统一放在[n+1] 48 for(int i=0; i<=n; i++){//插在i与i+1之间 49 // if(nodes[i].c != t && nodes[i+1].c != t) continue;//这里不能剪枝！！BBBAB这个可以在第一个B后插入一个A而全部消掉 50 //printf("insert %c after index %d\n", t, i); 51 nodes[n+1].next = nodes[i].next; 52 nodes[i].next = n + 1; 53 int cnt = 0; 54 bool updated = 1;//这趟扫描是否发生了消除 55 head = 0; 56 // printf("before disappear\n"); 57 // for(int j = nodes[head].next; j != -1; j = nodes[j].next){ 58 // printf("%c", nodes[j].c); 59 // } 60 // printf("\n"); 61 while(updated){//这趟扫描没有发生消除，则退出 62 updated = 0; 63 int discovered = 0; 64 int pre = head;//cur的前驱 65 int cur = nodes[head].next; 66 while(cur != -1 && nodes[cur].next != -1){//一趟自左到右的扫描 67 int j = nodes[cur].next; 68 //printf("%c %c\n", nodes[cur].c, nodes[j].c); 69 while(j != -1 && nodes[j].c == nodes[cur].c){ 70 updated = 1;//发现可消 71 discovered = 1;//发现了以cur为开始可消串 72 cnt++; 73 //printf("delete %c\n", nodes[j].c); 74 nodes[cur].next = nodes[j].next;//删除j 75 j = nodes[j].next; 76 } 77 if(discovered){//发现连续的cur,可消 78 cnt++;//加上开头的cur 79 discovered = 0; 80 nodes[pre].next = nodes[cur].next;//删除cur 81 cur = nodes[pre].next;//新的起点 82 }else{//未发现,cur只有一个 83 pre = cur; 84 cur = nodes[cur].next; 85 } 86 // printf("delete one cluster\n"); 87 // for(int j = nodes[head].next; j != -1; j = nodes[j].next){ 88 // printf("%c", nodes[j].c); 89 // } 90 // printf("\n"); 91 } 92 // printf("disappear once\n"); 93 // for(int j = nodes[head].next; j != -1; j = nodes[j].next){ 94 // printf("%c", nodes[j].c); 95 // } 96 // printf("\n"); 97 } 98 nodes[i].next = nodes[n+1].next;//删除插入的[n+1] 99 ans = max(ans, cnt); 100 //printf("ans this %d\n", cnt); 101 reset(); 102 } 103 } 104 printf("%d\n", ans); 105 } 106 return 0; 107 }
