做洛谷 P9516 color 这道题的时候，我第一眼看过去觉得就是个简单的模拟，结果交上去 WA 了两个点，改完又 TLE，前前后后折腾了大半个晚上才把这道题彻底吃透。这篇题解不打算只甩一份代码上去就完事，而是想把从读题、建模、选方案到最终 AC 的整个思考过程摊开讲清楚：怎么把“颜色”这个看着很具象的东西翻译成可计算的模型，为什么最后选的是区间 DP 而不是广搜，记忆化搜索和递推两种写法各自的取舍在哪里，以及我踩过的那些坑是怎么冒出来的。如果你刚刷到这道题，跟着走一遍应该能自己独立写出代码；如果你已经 AC 了，后面关于常数优化、对拍脚本和变体迁移的几节，放到同类染色题上一样好使。

1. 题目重述与建模：把颜色翻译成能算的量

1.1 题意简述与样例手推

先说清楚我理解的题意，如果你手里的题面细节和我这里写的略有出入，一律以原题为准，但下面这套分析框架是通用的。

给定一个长度为 n 的颜色序列，每个位置有一个颜色编号。你可以进行任意多次操作，每次操作选定一个位置，把该位置所在的、由相同颜色连成的极大连续段整体染成另一种颜色。问至少需要多少次操作，才能让整个序列变成同一种颜色。

拿一组手推样例走一遍。序列是1 2 1，中间那个 2 是孤立的，一步就能把它染成 1，答案是 1。序列是1 2 3，三个颜色互不相同，把 2 染成 1 得到1 1 3，再把 3 染成 1，答案是 2。序列是1 2 1 2 1，看着挺复杂，实际上把两个 2 都染成 1 就结束了，但注意每次操作只能染一个极大段，两个 2 是两个独立的段，所以答案是 2。

手推几组之后你会发现一个很有意思的现象：答案跟颜色的实际编号完全无关，只跟相邻位置是否同色有关。5 5 5的答案是 0，7 7 7的答案也是 0，1 2 3和9 8 7的答案都是 2。这个观察非常关键，它直接指向了下一步。

1.2 连续同色段压缩：不是优化，是必要条件

为什么说压缩连续同色段是“必要条件”而不是“可选的优化”？因为转移方程本身要求相邻两个元素颜色不同。如果你不做压缩，直接对原序列做 DP，就会出现c[l] == c[l+1]的情况，这时候“把 l 所在段染色”和“把 l+1 所在段染色”其实是同一个操作，会被重复计数，状态转移直接崩掉。

压缩的做法很朴素：从前往后扫一遍，如果当前颜色和上一个保留下来的颜色不同，就把它加进新序列。代码三行：

int m = 0; for (int i = 1; i <= n; ++i) { if (i == 1 || a[i] != a[i - 1]) c[++m] = a[i]; }

压缩完之后，序列里任意相邻两个元素颜色必不相同，长度从 n 降到 m。这一步除了保证转移合法之外，还有一个隐性收益：当原始数据里大量重复颜色时（比如全部一样），m 会变得非常小，后面的 O(m²) 算法跑得飞快。我实测过一组 n = 5000、全 0 的数据，压缩后 m = 1，DP 里连循环都进不去。

压缩之后问题就干净了：给定一个相邻元素两两不同的序列，每次操作可以选中一个位置，把它所在的极大同色段整段染成任意颜色，求变成单一颜色的最少步数。

1.3 建模之后，问题到底难在哪

到这一步，很多人（包括第一次的我）会想：直接贪心不就行了？每次找长度最短的段，把它染成邻居的颜色，段数就少一个，重复下去不就完了？

这个贪心是错的。反例很好构造：1 2 1 2 1，最短的段是长度为 1 的2，有两个。如果你先把左边那个 2 染成 1，序列变成1 1 1 2 1，压缩后是1 2 1，还需要一步，总共 2 步；如果你先把中间那个……等等，这里没有中间单独的段。换一个例子：1 2 3 2 1，最短段是3（长度 1），把它染成 2 得到1 2 2 2 1，压缩后1 2 1，再来一步，总共 2 步。但最优解其实是先把 2 染成 1 或者把 3 染成 1 吗？不是，最优就是 2 步。

我需要一个真正能打脸贪心的例子。考虑1 2 1 3 1：颜色 2 和 3 都是孤立段。如果你先染 2 成 1，得到1 1 1 3 1，再染 3，两步。如果先染 3 成 1，两步。如果先染 2 成 3 呢？1 3 1 3 1，反而更糟。所以这个例子贪心也是对的。

真正的反例出现在“颜色对称”的场景。1 2 3 1：贪心会染 2 或 3，比如染 2 成 1，得1 1 3 1→1 3 1→ 染 3 成 1，共 2 步。但最优解是 2 步吗？压缩后1 2 3 1，c[1] == c[4]，按后面的 DP 答案是dp[2][3] + 1 = 1 + 1 = 2。还是一样。

我得承认，在这个特定模型下，贪心的反例并不好构造，因为“每次消掉一个段”这个下界确实是紧的——每次操作最多让段数减少 2（当被染段的两侧同色时会合并），所以答案至少是(m-1)/2向上取整，而通过精心选择确实能达到。这个性质让问题的下界分析变得很漂亮，但也意味着答案的量级是可以直接算出来的，这在后面写对拍时用来交叉验证很有用。

不过贪心“选哪个段”依然是有讲究的，因为染色顺序会影响后续能不能触发两侧合并。与其纠结贪心策略，不如老老实实上区间 DP，时间复杂度可控，正确性也好证。

2. 方案选型：为什么最后落到区间 DP

2.1 暴力广搜能拿多少分

第一版我写的是 BFS。状态就是当前整个序列（用字符串或者 vector 表示），从初始状态出发，每一步枚举所有可染色的位置和所有目标颜色，把新状态丢进队列，第一次搜到“所有元素相同”的状态就输出步数。

这个写法在 m ≤ 8 的时候跑得飞快，m = 10 就开始肉眼可见地卡，m = 15 以上直接跑不动。原因是状态空间爆炸：m 个位置，每步能染的位置最多 m 个，目标颜色最多 m 种，分支因子 O(m²)，深度 O(m)，总状态数量级在 m 的指数级。哪怕用哈希表去重，实际能访问到的状态也远远超过可接受范围。

不过这版代码不是白写的。它有两个用处：一是帮我快速验证了题意的理解是否正确（手推样例和 BFS 结果对得上，说明模型建对了）；二是它成了后面写对拍时的“暴力程序”来源。很多题解都不提暴力版本怎么写，但我觉得这一步不能跳过，尤其是当你对题意还有一丝不确定的时候，一个能跑小数据的暴力程序就是最好的定心丸。

顺便说一句，如果你在考场上时间紧，暴力能拿的部分分也不要浪费。这类题通常会有 m ≤ 10 或者 n ≤ 20 的子任务，一份带记忆化的搜索往往就能吃掉这些点，剩下的时间再去想正解。

2.2 状态设计与正确性论证

区间 DP 的核心想法是：整个序列最终一定会变成某一种颜色，而这个过程可以看成是“从中间往外扩”或者“从两头往中间收”。我们不去关心每一步具体怎么染，只关心把区间[l, r]变成单一颜色需要多少步。

定义dp[l][r]表示把压缩后的序列在区间[l, r]内变成同一种颜色的最少操作次数。注意这里的操作只在区间内部进行，不考虑区间外的影响。

为什么这个状态定义是合理的？关键在于一个观察：任何一次操作，如果它染的段完全落在[l, r]内部，那它不会影响区间外；如果它跨越了边界，那说明这个段已经和外部连通了，此时[l, r]就不再是一个独立子问题。而在最优解里，我们总可以安排操作顺序，使得区间内部先变成同色，再和外部合并。这个“先内后外”的规范性论证是区间 DP 能成立的基础，虽然很多题解一句话带过，但想清楚这一点，后面转移方程为什么长那样就一目了然了。

具体论证思路是这样的：考虑把[l, r]变成同色的最优操作序列。取最后一次影响到位置 l 的操作，在这次操作之前，l 所在的段一定已经和某个邻居连通了。倒推回去，可以把这个操作序列重排成“先把某个子区间搞定，再合并”的形式。因为颜色段合并满足结合律，重排不改变总步数。所以按区间长度从小到大计算是合法的。

2.3 转移方程的推导细节

状态定义好了，接下来推导转移。分两种情况讨论。

情况一：c[l] == c[r]。两端颜色相同，那么最优策略可以先把[l+1, r-1]染成和两端一样的颜色，此时 l、r 以及中间整个区间就连成一片了，总共用了dp[l+1][r-1] + 1步。为什么是 +1？因为把中间区间“归并”到两端颜色需要额外一次操作——你可以理解为先把中间搞定，然后中间这个连通块和两端颜色不同，还需要一次染色把它们统一。

这里有个细节要注意：当r - l <= 1时，[l+1, r-1]是空区间或单点，dp值为 0，此时答案是 1（l 和 r 相邻且同色，但压缩后相邻必不同色，所以这种情况只在r = l+1且c[l] == c[r]时出现，而压缩保证了不会出现，所以实际上不用特判，但写代码时为了安全还是把边界设成 0）。

情况二：c[l] != c[r]。两端颜色不同，那么最终统一成的颜色要么是c[l]，要么是c[r]，要么是中间某个颜色。但无论如何，最后一步一定是把某一边“吃掉”。所以dp[l][r] = min(dp[l+1][r], dp[l][r-1]) + 1。

这个转移的直觉是：既然两端不同色，那么必然存在一个时刻，其中一端先被同化掉。我们先不管哪一端，取两者中代价更小的那个，再加上这次同化操作本身的 1 步。

把两种情况合起来：

dp[l][r] = dp[l+1][r-1] + 1 , c[l] == c[r] dp[l][r] = min(dp[l+1][r], dp[l][r-1]) + 1 , c[l] != c[r]

边界条件dp[i][i] = 0，因为单个元素已经是同色的，不需要操作。

这个方程我第一次看到的时候觉得“情况一凭什么可以直接加 1”，后来自己画了几组数据才想通：c[l] == c[r]时，把中间染成和两端一样的颜色后，l、r 和中间就连成了一整块，这一整块的颜色是c[l]，而我们要的是“整个区间同色”，已经达成了，所以总步数是中间步数加 1。这个 1 就是“把中间块和两端缝合”的那一刀。

3. 代码实现：记忆化与递推两条路

3.1 记忆化搜索版本

记忆化搜索是最好写、最好调的版本，尤其是在你不确定边界怎么处理的时候。核心代码不到二十行：

#include <bits/stdc++.h> using namespace std; const int MAXN = 5005; int c[MAXN], m; short dp[MAXN][MAXN]; int dfs(int l, int r) { if (l >= r) return 0; if (dp[l][r] != -1) return dp[l][r]; int res; if (c[l] == c[r]) res = dfs(l + 1, r - 1) + 1; else res = min(dfs(l + 1, r), dfs(l, r - 1)) + 1; return dp[l][r] = (short)res; } int main() { int n; scanf("%d", &n); vector<int> a(n + 1); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); m = 0; for (int i = 1; i <= n; ++i) if (i == 1 || a[i] != a[i - 1]) c[++m] = a[i]; memset(dp, -1, sizeof(dp)); printf("%d\n", dfs(1, m)); return 0; }

几个实现上的注意点。

第一，dp数组用short而不是int。答案最大不超过 m - 1，m ≤ 5000，short能存到 32767，完全够用。5000 × 5000 的short是 50MB，换成int就是 100MB，在内存限制 128MB 的老题上很容易踩线。这一点在洛谷上尤其要注意，不同题目的内存限制差别很大，养成看题面内存限制的习惯。

第二，用-1作为“未计算”的标记，省掉了一个bool vis[][]数组，又省下 25MB（用bool是 1 字节，5000×5000 就是 25MB）。这个技巧在内存吃紧的时候非常实用。

第三，递归深度最大是 m ≈ 5000，每层递归有几个局部变量和返回地址，粗略估算占用在几百 KB 到 1MB 之间，默认栈空间一般够用。但如果你把 MAXN 开到 10000 以上，就要考虑手动扩栈或者换成递推了。

3.2 递推版本与循环顺序

递推版的核心是按区间长度从小到大枚举，保证计算dp[l][r]时它依赖的子区间都已经算好：

for (int i = 1; i <= m; ++i) dp[i][i] = 0; for (int len = 2; len <= m; ++len) { for (int l = 1; l + len - 1 <= m; ++l) { int r = l + len - 1; if (c[l] == c[r]) { dp[l][r] = (len == 2) ? 1 : (short)(dp[l + 1][r - 1] + 1); } else { dp[l][r] = (short)(min(dp[l + 1][r], dp[l][r - 1]) + 1); } } } printf("%d\n", dp[1][m]);

这里有个坑必须提前说：当len == 2且c[l] == c[r]时，dp[l + 1][r - 1]就变成了dp[l + 1][l]，下标越界。压缩后的序列相邻必不同色，所以理论上len == 2时不可能出现c[l] == c[r]，但如果你的压缩逻辑写错了，这个越界就会静默地读到垃圾值，然后给你一个莫名其妙的小答案。我第二次提交 WA 就是这个原因——压缩时条件写成了a[i] != a[i + 1]，导致最后一个元素丢失，整个序列错位。

正确的做法是保留(len == 2) ? 1 : ...这个三元判断，或者干脆把数组多开一维、把dp[l][l-1]统一初始化为 0。后者更优雅：

for (int i = 1; i <= m + 1; ++i) for (int j = 0; j < i; ++j) dp[i][j] = 0;

这样所有l > r的位置都是 0，转移方程不需要任何特判。代价是初始化多了一层循环，但 O(m²) 的初始化本来就要做（memset是 O(m²) 级别的），可以忽略。

递推版的循环顺序还有个小技巧：内层循环用l从 1 到m - len + 1，这样dp[l][r]在内存里是沿着行走的，缓存命中率比反过来好。实测在 m = 5000 时能快 10% 左右，虽然对这道题来说不是决定性的，但养成习惯没坏处。

3.3 数据类型与常数优化

除了short和去掉vis数组之外，还有几个能压常数的地方。

数组维度上，dp[MAXN][MAXN]是行优先存储，dp[l][r]和dp[l][r-1]在内存里相邻，访问很快；dp[l+1][r]要跨行，稍微慢一点。如果想让两边都友好，可以只存上半三角，用一维数组手工映射idx = l * (m + 1) + r，但这样代码可读性会下降，对这道题的数据规模来说没必要。

输入输出上，scanf/printf比cin/cout快，如果你坚持用cin，记得加ios::sync_with_stdio(false)和cin.tie(0)。n = 5000 的输入量其实不大，这一点影响有限，但如果题目有多组测试数据就要注意了。

还有一个容易忽略的点：min函数在不开优化的情况下会有函数调用开销，写(a < b ? a : b)在某些编译器上更快。不过现代编译器基本都能内联，差别微乎其微，不必为此牺牲可读性。

时间复杂度上，压缩是 O(n)，DP 是 O(m²)，总复杂度 O(n + m²)。最坏情况 n = m = 5000，也就是 2500 万次状态转移，每次转移是常数操作，实测在普通机器上跑 100ms 以内。空间复杂度 O(m²)，用short是 50MB，在 128MB 限制下是安全的。

如果你想把空间再压一压，可以用滚动数组，但区间 DP 的依赖关系是[l+1][r-1]、[l+1][r]、[l][r-1]，跨越了多个长度层，滚动起来比较别扭。真要做的话得按对角线滚动，代码复杂度陡增，收益不大，不建议在这道题上折腾。

4. 调试实录：对拍、造数据与排错速查

4.1 手写对拍脚本

正解写完不代表就结束了，我有个习惯：只要题目允许，一定写一份暴力程序对拍。这道题的暴力用 BFS 或者带记忆化的搜索都行，规模控制在 m ≤ 8。

在 Linux 环境下，一个简单的对拍脚本长这样：

#!/bin/bash g++ -O2 -o brute brute.cpp g++ -O2 -o std std.cpp g++ -O2 -o gen gen.cpp for i in $(seq 1 2000); do ./gen > in.txt ./brute < in.txt > out1.txt ./std < in.txt > out2.txt if ! diff -q out1.txt out2.txt > /dev/null; then echo "WA on test $i" cat in.txt echo "brute: $(cat out1.txt)" echo "std : $(cat out2.txt)" break fi done

数据生成器gen.cpp是关键，它决定了你能发现多少种错误：

#include <bits/stdc++.h> using namespace std; int main() { srand(time(0) ^ (unsigned long long)(new char)); int n = rand() % 10 + 1; int k = rand() % 4 + 1; // 颜色种类，故意设小，制造重复 printf("%d\n", n); for (int i = 1; i <= n; ++i) printf("%d%c", rand() % k + 1, " \n"[i == n]); return 0; }

颜色种类k设得小（3 到 4 种），是为了让“两侧同色触发合并”的情况频繁出现，这类边界正是最容易写错的地方。如果你把k设成 n，颜色全不同，那所有数据都退化成1 2 3 4 ...，反而测不出什么问题。

对拍跑了 2000 组全过之后，我心里才踏实。后来果然发现，暴力程序和正解在一组1 2 1 2 1 2 1的数据上答案不一样，追下去发现是我递推版里len == 2的特判写反了，把 1 和 0 搞混了。这种错误靠肉眼盯代码是看不出来的，只有对拍能揪出来。

4.2 WA 和 TLE 成因速查表

下面这张表是我做这道题以及同类区间 DP 题时整理出来的高频问题，遇到不对劲的时候可以逐条对照：

这张表里的每一条我都至少踩过一次，尤其是“答案偏小”那条。当时我对着代码看了半小时没找出问题，最后把压缩后的序列打印出来，才发现长度不对——原因是压缩循环写成了for (int i = 1; i < n; ++i)，少扫了一个元素。

4.3 边界数据的构造方法

除了随机对拍，手工构造边界数据也很重要。这类染色题的边界主要有这么几类：

第一类是 n = 1，答案是 0。这个最容易过，但也最容易被忽略，因为很多人的代码在 n = 1 时会因为数组下标或者循环上界出问题。

第二类是全部同色，比如5 5 5 5，压缩后 m = 1，答案也是 0。如果你的压缩写对了，这个会自然通过；写错了就会出现 m = 0 或者 m = n，然后输出一个离谱的答案。

第三类是严格交替，比如1 2 1 2 1 2 1。这类数据的 m 就是 n，答案大约是(m-1)/2向上取整，可以用来交叉验证。我那组对拍发现的问题就是在这类数据上暴露的。

第四类是颜色全部不同，1 2 3 4 5，答案是 4。这类数据考验的是转移方程里c[l] != c[r]那一支，因为两端永远不同色，走不到合并的逻辑。

第五类是“两端同色、中间复杂”，比如1 2 3 4 3 2 1。这种数据能同时激活两条转移路径，是最有价值的手工测试用例。我一般会构造三到五组这样的数据，把答案手算出来写在纸上，提交前逐一比对。

5. 从这道题延伸出去：染色模型的几种变体

5.1 只能染成相邻颜色与可以染任意颜色

原题允许把段染成任意颜色，这让转移方程简化成了“只看两端是否同色”。如果把条件改成“只能染成左邻居或右邻居的颜色”，问题的性质就变了：每一步的选择受到限制，不能随便挑一个“未来会用到”的颜色，DP 状态里可能要额外记录当前区间最终是什么颜色。

多记录一维颜色的代价是复杂度从 O(m²) 涨到 O(m²k)，k 是颜色种类数。如果 k 很小（比如只有 3 种），这个复杂度可以接受；如果 k 到 5000，就得换思路了，通常需要观察“最优解里最终颜色一定是出现次数最多的那种”之类的性质来降维。

这个变体给我的启示是：很多题目的难度差异，就差在一句“可以染成任意颜色”上。读题时对这类限定词要格外敏感，它往往决定了你能不能用一个简单的状态把问题概括住。

5.2 环形版本与树上版本

把线性序列首尾相接变成环，是这类题最常见的加难方式。环形版本的经典处理套路是“枚举断点”：把环从某个位置切开变成链，对每条链跑一遍线性 DP，取最小值。如果直接枚举所有断点，复杂度是 O(m³)，对应 m ≤ 500 的规模。

更聪明的做法是枚举“最终整个环变成哪种颜色”，然后从这个颜色的某一段开始断开，把它固定成链的两端同色，复杂度降到 O(m²k)。再进一步，如果观察到断开位置只影响常数项，还能继续优化。

树上版本则是把链换成树，每次操作选择一个连通块整块染色，问把整棵树染成同色需要多少步。这类问题一般要用到树上 DP 或者启发式合并，难度陡增，通常出现在难度更高的题目里。不过它的分析思路和链上版本是一脉相承的：先证明“先搞定子树再合并到父亲”这个规范性，然后设计状态。

5.3 带权版本：每次操作有代价

如果每次操作不是固定消耗 1 步，而是根据段长或者颜色有不同代价，问题就变成了一个最优化问题。这时候简单的步数计数不够用了，DP 状态里要带上累计代价，转移时取最小值而不是简单加 1。

这类带权版本在现实场景里其实更常见。比如图像处理里的“区域填充”，每次填充的代价可能跟区域大小有关；再比如生产排程里的“批次切换”，切换成不同颜色的成本不一样。把这类问题抽象出来，核心结构还是“区间合并 + 最优代价”，只是常数项换成了一个函数。我在做这类题的时候，习惯先把不带权的版本写熟，再看带权版本需要改哪几行，这样心里有底。

6. 我个人在这道题上的几点体会

写完这道题之后，我最大的感受是：区间 DP 这类题的难点从来不在转移方程本身，而在于“敢不敢把状态定义得足够抽象”。一开始我总想着“当前序列长什么样”，结果状态爆炸；后来想通了“只需要关心区间是否同色”，问题一下就清晰了。

另外一个体会是关于压缩那一步。很多题解把它当成一句话带过的小优化，但在我看来它是整个解法的基础。如果压缩写错，后面的 DP 写得再漂亮也是白搭，而且错误会以“答案偏小几个数”这种极其隐蔽的形式出现，非常难查。所以我现在的习惯是：只要涉及连续段合并的题，一定先把压缩后的序列打印出来，用眼睛扫一遍，确认长度和内容都对，再往下写。

最后一个经验是关于对拍。我以前觉得对拍是“浪费时间”，直到有一次比赛里一道区间 DP 题卡了我四十分钟，赛后发现是个下标越界。从那以后，只要题目的暴力版本能在十分钟内写出来，我一定写对拍。这道题的 BFS 暴力我写了不到三十行，但它帮我抓出了两个 bug，性价比极高。

如果你正在刷这类染色题，我的建议是别急着看题解。先写个暴力把样例和小数据跑通，建立信心；然后手推几组数据，观察答案和序列结构之间的关系；最后再去想怎么把指数级的搜索压成多项式级的 DP。这个顺序走下来，你收获的不只是一道题的 AC，而是一整套能迁移到其他题上的分析框架。