题解 CodeForces 430B Balls Game 栈 C/C++

题目传送门：

Problem - B - Codeforceshttps://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可以销毁的最大数量的球。

示例

6 2 2
1 1 2 2 1 1

6

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，或，即将入栈的整体与栈顶整体颜色相同，且总元素数量 >= 3
			int 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;
}