UVA 10559 Blocks 是我当年刷区间 DP 时印象最深的一道题。第一次看到它时我以为只是个消消乐一排带颜色的方块每次选一段连续且颜色相同的方块消掉得分为这段长度的平方问全部消完最高能拿多少分。结果我按普通区间 DP 写了半个多小时样例反复不对后来才明白这个题的精髓根本不是“怎么消”而是“怎么故意不消”。它考察的核心是状态设计是为区间 DP 加一个额外维度去记录“暂时攒在手里”的同色方块。整道题的代码量很短但思维跳跃极大非常适合用来进阶区间 DP、锻炼记忆化搜索的状态抽象能力。不管你是准备 ICPC/CCPC 的选手还是自学算法刷 UVA/洛谷的朋友这篇题解都值得你认真看完。1. 题目解读这不是普通消消乐1.1 一句话题意与平方奖励的威力先明确题意有一排方块每个方块有颜色。每次操作可以选择一段连续且颜色相同的方块把它们全部消掉如果这次消掉了 k 个方块就得到 k² 分。目标是把所有方块消完求最大总得分。为什么用“平方”而不是“一次一块”或者“与长度成正比”因为平方奖励让问题瞬间变得反直觉。举个例子如果有两段长度都为 2 的同色方块它们中间被别的颜色隔开了。假如分两次消得分是 2² 2² 8但如果你先把中间的杂色方块消掉让这两段连在一起变成一段长度为 4 的大段再一次消掉得分是 4² 16。差距是 8 分而方块总数根本没变。正是这种非线性收益决定了整个题目的策略核心别急着消想办法把分散的同色方块攒到一起一次性吃掉。我常用一个更直观的例子来理解“平方奖励”。序列是1 1 2 1。如果从左往右硬消先消两个 1得 4 分再消中间的 2得 1 分最后消剩下的 1得 1 分总分 6。但正确的做法是先消中间的 2得 1 分此时三个 1 就连在了一起一次消掉得 9 分总分 10。你看只是交换了一次操作顺序总收益就从 6 涨到了 10。这就是平方奖励带来的“连击”逻辑。1.2 为什么简单区间DP会失效很多新手看到这类题第一反应就是定义dp[l][r]表示把区间 [l,r] 消完的最大得分。如果这是个普通合并模型比如矩阵链乘那枚举中间分割点就够了。但这里不行因为某个区间里的方块会和其他区间里的同色方块产生跨区间的合并。想象这样一个场景区间 [l,r] 左侧有一段长度为 len 的同色方块没有消。如果dp[l][r]只记录“消完 [l,r] 的得分”那它根本不知道左侧还挂着 len 个方块。等它消完 [l,r] 后左侧那些方块还是要单独消得分就变小了。而实际上你可能希望在消 [l,r] 的过程中通过先消掉中间的阻碍让左侧的 len 个方块和区间里的某个同色方块连成一片最后一起拿大分。换句话说普通区间 DP 假设左右子问题是独立的但本题中左右子问题因为“同色合并”而被强行关联了。你需要额外的信息来记录这种跨区间的依赖这就是多出来的那一维 len 存在的原因。1.3 第一步操作把连续段先压缩写代码之前有一个很重要的预处理将原始序列中连续且颜色相同的方块压缩成一个块同时记录这个块的颜色和长度。比如原始序列1 1 2 2 2 1 3压缩后变成(1,2), (2,3), (1,1), (3,1)。为什么要压缩如果不压缩同一个颜色内部还会出现很多不必要的分割DP 状态会非常混乱。而压缩之后相邻块的颜色一定不同我们的决策就变成了每次要么把当前最左边的块连同手里攒的同色方块一起消掉要么找后面某个同色块先把中间清空让它们合并。这个模型干净得多。压缩后块的数量最多就是原始 nn≤200所以状态数组的第一维和第二维按块编号来开完全够用。2. 状态设计dp[l][r][len] 是怎么想出来的2.1 关键洞察提前“攒”同色方块前面提到简单区间 DP 失效是因为跨区间合并。那么自然的想法就是我们能不能把“左侧已经攒下来、还没消掉的同色方块数量”也写进状态这个思路很像打游戏时憋大招。普通的区间的 DP 只关心“当前区间内部怎么消”而我们关心的是“在开始处理这个区间之前我手里已经攒了多少个和区间左端颜色相同的方块”。这些方块不会单独计算分数它们会跟着区间左端的处理一起消掉。所以定义如下核心状态dp[l][r][len]表示当前要处理从第 l 个块到第 r 个块这一段并且在它们的左边已经额外攒了 len 个颜色与 blocks[l] 相同的方块这 len 个方块等待和 blocks[l] 一起被消掉处理完这段后所获得的最大分数。注意这里的len不是块数而是原始方块个数。因为压缩后每个块可能长度大于 1攒起来的是具体数量。2.2 严格定义和两种转移有了这个状态我们就可以考虑第 l 个块到底怎么处理。它有两种选择。第一种选择不再等后面的同色块了直接把 blocks[l] 和左侧攒的 len 个方块一起消掉。因为 blocks[l] 本身长度为 cnt[l]所以这次消掉的方块总数是len cnt[l]得分是(len cnt[l])²。剩下的 [l1, r] 区间就没有左侧额外方块了所以转移是dp[l][r][len] (len cnt[l])² dp[l1][r][0]第二种选择在区间内找一个下标 k满足 k l且 blocks[k] 的颜色和 blocks[l] 相同。我们希望 blocks[l] 能“穿越”到 blocks[k] 那里并和它合并。要穿越中间 [l1, k-1] 的所有方块必须先被消干净这个区间的处理不带额外方块得分是dp[l1][k-1][0]。消完中间之后blocks[l] 和 blocks[k] 就相邻了同时左侧攒的 len 个方块也连上了于是手里的同色方块数量从len变成了len cnt[l]接下来要处理的区间变为 [k, r]。于是转移是dp[l][r][len] max( dp[l1][k-1][0] dp[k][r][len cnt[l]] )这里有个很关键的理解第二种转移里blocks[l] 并不是立刻和 blocks[k] 一起消掉而是把 blocks[l] 也“塞进”了左侧攒的方块堆里继续观察 blocks[k] 后面的情况。因为 blocks[k] 后面可能还有同色块等着合并我们把这个决定推迟到dp[k][r]内部去做。这种“推迟决策”的方式正是解决跨区间合并的妙处。2.3 转移方程的推导思路为什么第一种转移要加上dp[l1][r][0]因为一旦 blocks[l] 被消掉左边攒的那些 len 个方块已经被算进分数了所以剩下的区间只能从零开始没有额外的同色方块可用。为什么第二种转移中间区间用dp[l1][k-1][0]而不是dp[l1][k-1][len]因为左侧攒的 len 个方块颜色是 blocks[l] 的颜色它要和 blocks[l] 一起走绝不会去帮助清除中间那些不同色的杂块。中间那段是被彻底清空的所以它不享受任何左侧加成。不理解的话可以想象一个推箱子的场景。blocks[l] 是一个红色的“资源包”左侧 len 个红色方块都是它的货物。现在它要向右移动到 blocks[k] 那里中间的路必须搬空。搬空了之后它自己身上的货物len 个方块加上它本身cnt[l]才算完成一次“扩容”继续向右寻找下一个同色目标。2.4 复杂度看着吓人跑起来还行状态总数大约是块数 m 的平方乘以 len 的可能取值也就是 O(n³)。每个状态转移时要在区间内寻找同色块最多再花 O(n)所以理论复杂度是 O(n⁴)。n200 时满打满算是 1.6e9 量级听起来有点吓人。但实际代码跑起来远没有这么恐怖。首先是记忆化搜索并不会访问所有状态很多(l, r, len)组合根本不会出现其次我们在枚举 k 时只考虑和 blocks[l] 颜色相同的块区间内同色块数量并不多。我用记忆化搜索实现在 UVA 原始数据下一般几百毫秒到 1 秒左右就能通过属于一种“理论大、实际稳”的典型 DP。3. 记忆化搜索实战从建模到AC3.1 预处理代码连续段压缩先写出压缩逻辑。我是用结构体把每个块的颜色和长度存下来最后得到一个vectorBlock。struct Block { int col; int cnt; }; vectorBlock b; void compress(const vectorint a) { b.clear(); int n a.size(); for (int i 0; i n; ) { int j i; while (j n a[j] a[i]) j; b.push_back({a[i], j - i}); i j; } }这里容易犯的错是压缩时循环增量写错导致段边界没处理好。建议写完压缩后先输出一遍b检查相邻块颜色是否一定不同。3.2 递归函数实现细节状态用三维数组dp[l][r][len]存l 和 r 是压缩后块的编号len 是已经攒的原方块个数。因为 n ≤ 200直接开dp[205][205][205]。递归函数写起来非常短int dfs(int l, int r, int len) { if (l r) return 0; int res dp[l][r][len]; if (res ! -1) return res; // 直接消掉当前的 blocks[l]连同左侧攒的 len 个方块 res (b[l].cnt len) * (b[l].cnt len) dfs(l 1, r, 0); // 找后续同色块合并 for (int k l 1; k r; k) { if (b[k].col b[l].col) { res max(res, dfs(l 1, k - 1, 0) dfs(k, r, len b[l].cnt)); } } return res; }如果你不习惯int res dp[l][r][len]这种写法可以先读旧值再赋值效果一样。但引用能避免手滑漏掉最后一步的return。3.3 完整可提交代码把上面拼起来加上多组输入处理就是一份完整可提交的代码。#include bits/stdc.h using namespace std; struct Block { int col; int cnt; }; vectorBlock b; int dp[205][205][205]; int dfs(int l, int r, int len) { if (l r) return 0; int res dp[l][r][len]; if (res ! -1) return res; res (b[l].cnt len) * (b[l].cnt len) dfs(l 1, r, 0); for (int k l 1; k r; k) { if (b[k].col b[l].col) { res max(res, dfs(l 1, k - 1, 0) dfs(k, r, len b[l].cnt)); } } return res; } int main() { int n, cas 1; while (scanf(%d, n) n) { vectorint a(n); for (int i 0; i n; i) { scanf(%d, a[i]); } b.clear(); for (int i 0; i n; ) { int j i; while (j n a[j] a[i]) j; b.push_back({a[i], j - i}); i j; } memset(dp, -1, sizeof(dp)); int ans dfs(0, (int)b.size() - 1, 0); printf(Case %d: %d\n, cas, ans); } return 0; }UVA 10559 的输入格式是多个测试用例最后一行是 n0。如果你是在其他 OJ 上做这道题输入格式可能会改成第一行是测试组数 T只需要调整外层循环就好核心 DP 逻辑完全一致。3.4 边界、初始化与多组输入递归终止条件l r表示空区间返回 0。这里不需要额外处理l r的情况因为转移中如果找不到同色块 kres 会直接取第一种转移(b[l].cnt len)² dfs(l1, r, 0)而后面的空区间返回 0结果就是消掉最后一个块及左侧攒的方块。这实际上就覆盖了l r的情况。初始化用memset(dp, -1, sizeof(dp))原因后面会详细讲。每次 case 都要清空因为不同测试用例之间的方块数据完全不同。还有一个小细节dp数组的第三维大小不能只开到压缩后的块数 m而应该开到原序列长度 n。因为len累计的是方块总个数不是块数。比如某个颜色在原序列里出现 180 次压缩后可能只有 3 个块但 len 完全可以累计到 180如果数组只开到 50就会越界。4. 调试实录我踩过的坑和排查方法4.1 记忆化数组初始化的坑第一次写这题时我习惯性用memset(dp, 0, sizeof(dp))初始化结果正确性出了问题。原因很简单有些合法状态的分值是 0比如空区间返回 0。如果用 0 当作“还没计算”的标记那么真的算出 0 的状态就无法和未计算状态区分会导致本该递归计算的子问题被直接当成答案返回结果全部错乱。所以记忆化数组要么初始化为-1要么用时间戳数组。本题的所有真实答案除了空区间都是正数用 -1 很安全。memset(dp, -1, sizeof(dp));4.2 不要把“块数”和“原方块数”搞混这个坑比较隐蔽。压缩后每个块的长度可能超过 1而 DP 状态里的 len 表示“原方块个数”。所以转移里b[l].cnt是块长度len b[l].cnt是“左侧攒的方块数 当前块长度”(b[l].cnt len)²才是得分。有些人会把b[l].cnt当成 1 来写认为反正压缩后每块都是连续同色就大意了。比如一个长度为 5 的同色块消除时得分应该是 25 而不是 1。压缩只是为了简化状态长度信息必须保留。4.3 用时间戳代替 memset 的优化当测试用例特别多时每次memset一个 205×205×205 的数组大约是 8MB 的清零操作累计起来是有一定开销的。如果遇到时限很紧的 OJ可以用一个二维的时间戳数组替代int dp[205][205][205]; int vis[205][205][205]; int tim 1; int dfs(int l, int r, int len) { if (l r) return 0; if (vis[l][r][len] tim) return dp[l][r][len]; vis[l][r][len] tim; // 正常计算并存入 dp[l][r][len] ... }每处理一个 case 前tim这样就不用清空整个 dp 数组了。不过 UVA 10559 数据量不大memset也能过这个技巧大家按需使用即可。4.4 常见错误速查表症状可能原因解决方案样例输出偏小压缩时合并错误或转移时把得分计算成了线性而不是平方逐段检查压缩结果确认使用(cnt len)²答案完全不对dp 数组初始化为 0未计算状态被当成 0 返回初始化为 -1数组越界或 RElen 维度只开到块数而不是原序列长度第三维开到 n1 或 205Case 编号少了一个多组输入结束条件用错确认while(scanf(%d,n) n)递归调用过深len 累计过大状态爆炸检查是否漏了压缩或 len 是否误加了所有块的长度还有一个经验如果答案差一点点优先怀疑是dfs(k, r, len b[l].cnt)里的区间写成了dfs(k, r, len cnt[k])。这个错误特别隐蔽因为思路一旦进入“合并”状态很容易把两个块的信息搞混。5. 变式题、训练路线与个人心得5.1 和这题一脉相承的题目如果你能把 UVA 10559 吃透你会发现很多“祖玛类”消除题都用了几乎一样的模型。第一道必提的是 POJ 1390 Blocks它们其实是同一道题只是平台不同。如果你在 POJ 上刷过这题会发现大家的讨论和 UVA 10559 基本重合。第二道是 Codeforces 1107E Vasya and Binary String。它给你一个 01 串每次可以删一段任意连续子串删掉长度为 x 的段得 w[x] 分问全部删完的最大得分。做法就是把 01 串压缩成连续段然后 dp[l][r][len] 表示区间 [l,r] 左侧还有 len 个与左端相同的字符可以一起删除转移和 UVA 10559 不能说一模一样只能说完全同构。所以不要把这题当成孤立的例题它是一个模型原型。会了这一题等于掌握了一类“带外部附加资源的区间消除 DP”。5.2 从UVA 10559学到的通用DP套路我大学时期刷 DP 的一个体会很多区间 DP 难题难点不是转移方程的代码而是“怎么想到要加一维”。UVA 10559 给了一个很好的示范。当你发现一个区间 DP 的答案还和区间外部的某个状态有关时不要硬靠枚举分割点去解决。想想能不能把这个外部状态直接写进 dp 下标里。常见做法就是加一个维度比如“左边已经攒了多少同色的资源”“已经连续选了几个”等。这本质上是用空间换信息把原来流失的信息补齐。这一招不仅用于消除类题目在很多字符串 DP、序列 DP 里也非常常用。另外写这种记忆化搜索时我习惯先写终止条件再写最朴素的转移最后才考虑加不加缓存。原因很简单先保证递归逻辑正确再优化重复状态。如果一开始满脑子都是“记忆化”很容易把边界条件搞乱。5.3 最后的一点刷题经验我个人在实际练习中的体会是UVA 10559 是一道非常适合“自我检验”的题目。如果你能不看题解独立推导出dp[l][r][len]这个状态那你的区间 DP 就算是真正入门了。如果你看了题解才懂也没关系但一定要亲手把几个小例子走一遍状态转移比如1 1 2 1从dfs(0, 3, 0)出发一步步看它是先消 2 再消 1 的。这个过程比背十道模板题都管用。最后再分享一个小技巧刷题时如果样例能过但提交超时别急着优化常数先看状态是不是真的被访问到了。拿这道题来说如果你在递归函数里打印l, r, len会发现大量的状态根本没有出现。很多“超时”其实不是状态多而是你的转移里枚举了太多不可能的情况。学会用打印信息分析递归路径是竞赛调试的基本功。