最近在洛谷上翻 NERC 2019 的题目，看到 P12935 这道Balls of Buma，第一反应是“哦，又一个祖玛变种”。这类题在区域赛里其实不少见，表面是个点击消除的小游戏，实际是披着字符串壳子的区间 DP。整道题不需要什么高级数据结构，压缩完连续段之后，一个二维 DP 就能跑完，非常适合拿来练区间 DP 以及“消除类问题”的通用套路。这篇文章我会完整拆解这道题的思考过程、状态设计、代码实现，还有我实际调试时踩过的几个坑，希望能给准备区域赛、或者想系统刷区间 DP 的朋友一点参考。
1. 题目是干什么的：一场能“连锁反应”的祖玛游戏
1.1 题目背景与读题要点
NERC 2019 是欧洲区域赛体系里的一场比赛，题目质量普遍在线，尤其是前几道题，经常会把一个很简单的游戏规则包装成需要动态规划的模型。这道Balls of Buma是其中的 B 题，规则描述非常简洁：有一排球，每个球有颜色，你可以任意插入一个球到任意位置，如果插入后某个位置出现连续 3 个或以上的同色球，这一整段同色球就会全部消失，剩余部分向中间靠拢；如果靠拢之后又形成连续 3 个同色，会继续连锁消除。问最少插入几次可以把整排球全部消掉。
这里有几个关键词必须抓准，漏一个都会让思路跑偏：
- 插入的球颜色可以任意选，不一定非要和旁边的球同色。比如在一个
A旁边插入B是完全允许的，只是不一定有用。 - “连续 3 个”是触发条件，但一旦触发，消失的是“一整段连续同色球”，不是说只消 3 个，剩下的还留在原地。这是很多人第一次做这类题最容易理解错的地方。
- 消完靠拢后有可能继续连锁。比如
AAABBBAAA这种串，如果先把中间的BBB触发消掉，两侧的AAA就会靠拢成 6 个A，又满足触发条件，自动消除。
读题时如果只看到“消除连续 3 个”，没有把“整段消失”和“靠拢连锁”这两条规则刻进脑子里，后面写 DP 的时候就会反复出错。
1.2 先手玩两个例子找感觉
看一个最简单的样例：AABBBAA。直接插入一个B到中间的BBB块里，串变成AABBBBAA，这时连续B有 4 个，满足触发条件，整个 B 段全部消失。剩下的AAAA是左右两段A靠拢后新形成的连续段，长度是 4，又满足触发条件，于是自动消除。整个过程只插入了 1 个球。所以这个答案是 1，而不是 3。
再看ABCBA这种带点回文味道的串。如果从头开始乱插，很容易算成 5、6 次。最优做法可以是：先在某个B旁边插入一个B，让一段B变成 3 个，触发消除；剩下ACA之后，中间的C需要补 2 个C才能消除，两侧的A还需要再补 1 个A才能合并消除，总共 4 次。如果把字符串压缩成块，就是A1 B1 C1 B1 A1。这里最精彩的地方在于，左右两个B并不相邻，却能在消除完中间的C之后“隔空联手”，这个现象提示我们必须用区间的视角去考虑问题，而不能只看局部。
这两个例子还说明了一件事：为什么不能简单贪心。如果只盯着当前最大的连续块去补，AAABBAAA这种串会让你先补 A、再补 B、再补 A，算出来至少 3 次；但真实最优解是直接触发中间的 B，让两个 A 大块合并自动消除，只要 1 次。贪心算法看不到这种“跨块合并”的收益，必须交给区间 DP 去枚举。
2. 核心思路：压缩成块，再用区间DP拼答案
2.1 为什么要压缩连续同色块
先想一个问题：一排球里，连续的AAA和单独的A，在“触发”这件事上到底有什么区别？其实只有“数量够不够 3”的区别。既然触发之后整个连续同色段一起消失，那么我们完全可以把每一段连续同色球压缩成一个“块”，块里记录颜色和数量。比如AABBBAA压缩成(A,2), (B,3), (A,2)，ABCBA压缩成(A,1), (B,1), (C,1), (B,1), (A,1)。
这一步压缩带来的好处非常明显：原串可能有几百上千个字符，但连续的相同字符被压成一块之后，真正需要做决策的“块数”会大幅减少。在区间 DP 里，状态数量是 O(m^2)，m 是压缩后的块数，如果 m 能降到几十甚至几百，DP 就非常轻松。更重要的是，把连续同色段看成一个整体之后，我们不再关心块内部的细节，只关心“这个块有多少个球”“这个块是什么颜色”“这个块要不要被触发”，思考的粒度直接从字符上升到了段。
这也是所有“消除类”题目的通用第一步：先压缩，再看能不能变成区间上的问题。洛谷上绝大多数祖玛变种、消消乐变种，都能用这个套路打开局面。
2.2 单块的最少插入次数
在写区间 DP 之前，必须先解决好一个最简单的问题：如果整排球只剩一个块，最少要插入几次？
分三种情况讨论：
- 块内数量为 1，比如单独一个
A。需要再插入 2 个A，凑成AAA，然后触发消除，答案是 2。 - 块内数量为 2，比如
AA。插入 1 个A，变成AAA，触发消除，答案是 1。 - 块内数量为 3 或更多，比如
AAA、AAAAA。注意这里答案仍然是 1，而不是 0。因为没有任何人插入的时候，这个块不会自己消失；至少需要插入 1 个同色球，让整段长度变成 4 或 6，仍然大于等于 3，之后整段一起消失。
所以单块的初始化公式可以写成：
dp[i][i] = (cnt[i] >= 3 ? 1 : 3 - cnt[i])这个公式虽然简单，但它是整个 DP 的地基。很多人会在这里把cnt[i] >= 3的情况初始化成 0，结果后面所有依赖它的区间答案全都少算 1，而且非常难查出来。
2.3 区间DP：状态怎么定义
设dp[l][r]表示把压缩后的第l块到第r块全部消除所需的最少插入次数。
这里“全部消除”的含义要理解
