尧图网站建设 
最近在洛谷上翻 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块全部消除所需的最少插入次数。这里“全部消除”的含义要理解 Balls of Buma题解：字符串压缩与区间DP破解祖玛消除
最近在洛谷上翻 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块全部消除所需的最少插入次数。这里“全部消除”的含义要理解