题目传送门：
Problem - B - Codeforces
https://mirror.codeforces.com/contest/430/problem/B翻译：
Iahub正在为国际信息学奥林匹克竞赛（IOI）做准备。有什么比玩一个类似祖玛的游戏更好的训练方法呢？
一排中有n个球。每个球都染着k种颜色中的一种。最初，这一排球中不会有三个或三个以上连续相同颜色的球。Iahub有一个颜色为x的球。他可以将他的球插入排列中的任意位置（可能是在另外两个球之间）。如果任何时刻排列中有三个或三个以上连续相同颜色的球，它们将立即被销毁。这个规则会被多次应用，直到没有更多连续三个或三个以上相同颜色的球。
例如，如果Iahub有一排球[黑, 黑, 白, 白, 黑, 黑]和一个白球，他可以将球插入两个白球之间。这样三个白球被销毁，然后四个黑球变得连续，所以所有四个球都被销毁。最终排列中将不再有任何球，因此Iahub可以销毁所有6个球。
Iahub希望尽可能多地销毁球。给定球排列的描述以及Iahub的球的颜色，通过告诉他他可以销毁的最大数量的球来帮助Iahub为IOI做准备。
输入
输入的第一行包含三个整数：n（1 ≤ n ≤ 100）、k（1 ≤ k ≤ 100）和x（1 ≤ x ≤ k）。接下来一行包含n个空格分隔的整数c1, c2, ..., cn（1 ≤ ci ≤ k）。数字ci表示排列中第i个球的颜色为ci。
保证初始球排列永远不会包含三个或三个以上连续相同颜色的球。
输出
输出一个整数 — Iahub可以销毁的最大数量的球。
示例
| Input | Output |
|---|---|
6 2 2 1 1 2 2 1 1 | 6 |
| Input | Output |
|---|---|
1 1 1 1 |
思路：
祖玛游戏/一维消消乐，找到一个消除点，并向两端扩展
可以在脑中想象一下这个过程，这和括号序列匹配很像
事件之间都是完全包含关系，不难想到，可以用栈解决
此外，将相连的相同颜色的球视为一个整体 (一个括号)
会使我们处理起来方便得多，因此我们先对输入的内容做一个预处理，将颜色相同的球合并
结构体 A 的一个对象就是相连的相同颜色的球的一个整体
color 表示整体的颜色，num 表示整体包含的球的数量
将预处理结果存入 arr，然后遍历 arr，寻找可以消除的位置，之后进行 "括号序列匹配"
细节见代码
代码：
#include <algorithm>
#include <iostream>
using namespace std;
struct A { int color, num; } arr[105], stk[105];//stk 是一个临时的栈，每次循环开始都会清空
int n, k, x, pre, input, top = -1, ans;//pre 在预处理时记录上一次的输入，pre 与输入 input 相同时，合并相同颜色，否则新建一个整体。pre 初始值要和所有颜色都不相同
int main()
{cin >> n >> k >> x;for (int i = 0; i < n; i++)//预处理{cin >> input;if (input != pre) arr[++top] = { input, 1 };//不同颜色新建一个整体else arr[top].num++;//合并相同颜色pre = input;}for (int i = 0; i <= top; i++)//遍历，寻找能够消除的位置。枚举所有情况{if (arr[i].color == x && arr[i].num >= 2)//整体颜色与 x 相同，且整体元素数量 >= 2 时，可以消除{arr[i].num++;//将 x 合并到整体里，然后创建一个临时的栈 stk，从头开始做 "括号序列匹配"//只不过匹配成功进行消除的条件是：整体元素数量 >= 3，或，即将入栈的整体与栈顶整体颜色相同，且总元素数量 >= 3int t = -1, cnt = 0;//t 指向栈顶元素，每轮枚举都从栈为空开始。cnt 统计该轮消除的球的数量for (int j = 0; j <= top; j++)//"括号序列匹配"{if (arr[j].num >= 3) cnt += arr[j].num;else if (t == -1 || arr[j].color != stk[t].color) stk[++t] = arr[j];else{stk[t].num += arr[j].num;if (stk[t].num >= 3) cnt += stk[t--].num;}}arr[i].num--;//恢复现场，参考 DFS 中回溯后要进行的操作，这样不影响下一轮枚举ans = max(ans, cnt - 1);//答案不包含 x 本身，所以 ans 更新时和 cnt-1 比较}}cout << ans;return 0;
}
