问题简介

具体参照 hihocoder网站。

实现思路

因为字符串长度最大为100，只有ABC三个字符，所以只有300种情况，每种情况最差处理是O(100^2)。所以即便最差情况也只有3e6的计算次数，不足10ms。 因此只需要实现穷举算法即可，先插入字符，然后判断会消除多少字符。

代码

1. 消除字符的函数

输入字符串，返回消除字符的数目，同时字符串改变为消除之后的字符串。例如str="ABCBCCCAA",函数值返回为5，str变为"ABCB"。 int eliminate(char *str){ int len = strlen(str); int result = 0; char pre = 0; bool flag[102] = {false}; for (int i = 0;i < len;++i){ if (str[i] == pre || str[i] == str[i+1]){ flag[i] = true; ++result; } pre = str[i]; } if (result > 0) { char *p = str; for (int i = 0;i < len;++i) if (!flag[i]) *p++ = str[i]; *p = 0; return result + eliminate(str); } else return 0; }

2. 计算插入之后最多消除的字符串

输入字符串，返回通过插入字符可以得到的最多消除字符数目。是枚举在所有位置上插入ABC的所有情况，返回其中的最大值。 int cal2(char *str){ int len = strlen(str),result = 0,tmp; char tmp_str[102] = ""; for (int i = 0;i < len+1;++i){ for (char j = 'A';j < 'D';++j){ for (int k = 0;k < i;++k) tmp_str[k] = str[k]; tmp_str[i] = j; for (int k = i;k < len;++k) tmp_str[k+1] = str[k]; tmp_str[len+1] = 0; tmp = eliminate(tmp_str); if (tmp > result) result = tmp; } } return result; }

3. 主函数

只是输入输出，此处跳过。

后记：记录一个错误的算法以及发现反例的代码

1. 错误的算法

先消除字符串，然后再插入字符消除。初心是减少枚举的次数，但是反例是"AABA"。 int cal_highest_score(char *str){ char tmp_str[102] = ""; strcpy(tmp_str,str); int eli = eliminate(str); int eli2 = 0,j; int len = strlen(str); for (int i = 0;i < len;++i){ j = 0; for (j = 1;i-j > -1 && i+j < len && str[i-j] == str[i+j];++j); --j; if (eli2 < j*2+1) eli2 = j*2+1; } strcpy(str,tmp_str); return eli + eli2 + 1; }

2. 发现反例的代码

枚举所有字符长度小于100且只含有ABC字符的字符串，比较正确函数与错误函数的结果以得到反例。 int main() { char str[102] = {0}; int depth = 0,tmp; while (depth > -1){ if (str[depth] == 'C' || depth > 100){ str[depth] = 0; --depth; } else { str[depth] = (str[depth] == 0)?'A':(str[depth]+1); str[depth+1] = 0; if (cal2(str) != cal_highest_score(str)){ cout << "Error:" << str << '\t' << cal2(str) << '\t' << cal_highest_score(str) << endl; cin >> tmp; } ++depth; } } }