「Blocks」消木块

形式化题目

一列 $n$ 个木块，第 $i$ 个木块有颜色 $c_i \in [1, n]$ 。

一次操作：选一个木块，把它以及与它相邻且同色的所有木块一起删除；这次删掉 $k$ 个木块得 $k^2$ 分。删除后左右两段靠拢，可能形成新的相邻同色段。

求把 $n$ 个木块全部删完能得到的最大总分。

例如 1 2 2 2 2 3 3 3 1 的最高分是 $29$ ：把 4 个 2 和 3 个 3 分别删掉（谁先谁后都行， $16 + 9$ ），剩下的两个 1 靠拢后一起删（ $4$ ），共 $29$ 。关键是这串里本来只有一个 1 在左端、一个 1 在右端，它们必须等中间的木块清空后才能合到一起。

为什么不能贪心：每次删掉当前最长的一段是错的。1 1 2 1 里贪心先删 11 得 $4$ ，最后 $4+1+1=6$ ；最优是先删 2，让三个 1 靠拢，得 $1+9=10$ 。所以“先删掉碍事的小段、把同色木块攒大”才是关键，必须枚举顺序。

正解

思路

第一步：把相邻同色的木块压成一段

相邻同色的木块永远不该分开删——若某次删了左边 $x$ 个、另一次删了右边 $y$ 个，而它们之间没有别的木块，那把它们合成一次删掉得 $(x+y)^2 \geqslant x^2+y^2$ 分，只会更优。所以先把木块列压缩成颜色段：

s_0, s_1, s_2, \dots, s_{m-1}, \qquad s_i = \text{第 } i \text{ 段里的木块数}.

样例 1 2 2 2 2 3 3 3 1 压成 $s = [1,4,3,1]$ ，颜色 $[1,2,3,1]$ ， $m = 4$ 。删掉第 $i$ 段至少得 $s_i^2$ 分。

第二步：状态里必须记“右边挂了多少同色木块”

一次删除一定是若干个整段的并集，这些段在删除的那一刻两两相邻，说明它们之间的段都已经被提前删空了。现在固定一个区间 $[i, j]$ ，看段 $j$ 那一侧的边界：将来删掉段 $j$ 的那一次删除，还可能把右边的若干同色段一起带上（它们现在在 $[i,j]$ 外面，等右边的段都被删空、它们与 $j$ 靠拢后就能合并）。于是真正影响最后得分的，只有两件事：

现在还在考虑的段是哪一段连续区间 $[i, j]$ ；
段 $j$ 那一次删除还会额外带上右边多少个同色木块 $k$ 。

中间那些被提前删掉的段只贡献一个分数，细节不再重要——这就是重复子问题的来源，也是朴素搜索（把整条序列当状态）指数爆炸的原因。

定义

f(i, j, k) = \text{消掉颜色段 } i..j \text{ 的最高分，其中段 } j \text{ 那一次删除额外带上右边 } k \text{ 个同色木块}.

也就是说，段 $j$ 最终是和 $s_j + k$ 个同色木块一起被消掉的。最终答案是 $f(0, m-1, 0)$ 。

第三步：只处理最右边的段 j

每次盯着区间右端的段 $j$ （这样剩下的子问题区间一定更小），它在那次删除中只有两种命运。

转移一：段 $j$ 的这次删除不牵涉区间里任何别的段。 于是 $i..j-1$ 全部先被独立删空，段 $j$ 带着右边那 $k$ 个同色木块一起消掉：

f(i,j,k) \leftarrow f(i, j-1, 0) + (s_j + k)^2 .

转移二：段 $j$ 的这次删除还包含左边的某个同色段 $p$ 。 取 $p$ （ $i \leqslant p < j$ ）为这次删除里段 $j$ 左侧编号最大的段，则 $p$ 与 $j$ 必然同色。为了让 $p$ 与 $j$ 在删除时相邻，中间的 $p+1..j-1$ 必须先被独立删空：这截夹在 $p$ 和 $j$ 中间，被 $p$ 和 $j$ 夹住，接不到外面的木块，所以它的 $k$ 只能是 $0$ ：

f(i,j,k) \leftarrow f(i,\,p,\,k+s_j) + f(p+1,\,j-1,\,0),\qquad p \in P_j,\ p \geqslant i .

其中 $P_j$ 是段 $j$ 前面所有与它同色的段号。第一项是本问题的“剩余部分”：段 $p$ 右边现在挂了 $s_j$ 个来自段 $j$ 的木块，再加上原来的 $k$ 个；第二项是那截“被夹在中间的段”。当 $p = j-1$ 时第二部分是 $0$ 。

f(i,j,k)= \begin{cases} (s_i+k)^2, & i=j,\\[4pt] \max\Bigl(f(i,j-1,0)+(s_j+k)^2,\ \max\limits_{p\in P_j,\,p\geqslant i}\bigl[f(i,p,k+s_j)+f(p+1,j-1,0)\bigr]\Bigr), & i<j. \end{cases}

用样例看这个 DP

样例压成 $s = [1,4,3,1]$ ，颜色 [1,2,3,1]，所以只有段 3 有“前面的同色段”： $P_3 = \{0\}$ 。

各段的 $s_i$ 与 $P_i$ ：

段 $i$	0	1	2	3
颜色	1	2	3	1
$s_i$	1	4	3	1
$P_i$	$\varnothing$	$\varnothing$	$\varnothing$	$\{0\}$

$k = 0$ 状态的计算结果（行是 $i$ 、列是 $j$ ，空表示 $i > j$ ）：

$i \backslash j$	0	1	2	3
0	1	17	26	29
1		16	25	26
2			9	10
3				1

读表的顺序是从左上到右下（区间由短到长）。最关键的最后一格：

转移一： $f(0,2,0) + (s_3+0)^2 = 26 + 1 = 27$ ；
转移二（ $p = 0$ ）： $f(0,0,0+s_3) + f(1,2,0) = f(0,0,1) + 25 = 4 + 25 = \mathbf{29}$ 。

$f(0,0,1) = (s_0+1)^2 = 4$ 正是“段 0 收下段 3 之后，两个 1 一起删”； $f(1,2,0) = 25 = 16+9$ 是中间那截（4 个 2 和 3 个 3）独立解决的分数。两者相加就是样例答案。

再看 $f(1,2,0) = 25$ 本身：段 2 没有前面的同色段，只能走转移一， $f(1,1,0) + 9 = 16 + 9 = 25$ 。

为什么用记忆化搜索而不是递推

递推当然可以（按区间长度递增，每个区间维护一张 $k$ 的表），但要手工排好 i、j、k 的遍历顺序并为每个区间开数组。关键在于 $k$ 只有真实可达的取值才有意义——它是若干段长度之和，不是 $0 \sim n$ 的所有整数。用 functools.cache 让递归自己决定访问顺序，既不用给 k 定维，代码也短得多。

EARLIER[j] 存的是 $P_j$ 从近到远的段号（严格递减），于是循环里一旦 p < i 就可以直接 break，不必扫完整个列表。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 13:00
 * update_at: 2026-10-10 13:00
 */

// 消除木块：区间 DP，先把同色相邻块压成颜色段
#include <cstdio>
#include <vector>
using namespace std;

typedef long long ll;

int seg_cnt;                 // 颜色段个数
vector<int> seg_size;        // 第 i 段里有几个木块
vector<vector<int> > earlier; // earlier[j]：第 j 段前面同色的段号，从近到远严格递减
vector<int> memo;            // f(i,j,k) 的记忆化表，-1 表示未算
int dim;                     // memo 每一维的大小（可用的 k 上界 + 2）

int idx(int i, int j, int k) {
    return (i * dim + j) * dim + k;
}

// 消掉颜色段 i..j 的最高分；段 j 这一次消除还会额外带上右边 k 个同色木块
int f(int i, int j, int k) {
    int& res = memo[idx(i, j, k)];
    if (res >= 0) {
        return res;
    }
    if (i == j) {
        int t = seg_size[j] + k;
        res = t * t;
        return res;
    }
    res = f(i, j - 1, 0) + (seg_size[j] + k) * (seg_size[j] + k); // 段 j 单独消
    for (int t = 0; t < (int)earlier[j].size(); t++) {
        int p = earlier[j][t];
        if (p < i) {
            break; // earlier[j] 递减，再往前都越界了
        }
        // 段 j 这次消除还包含左边的同色段 p：中间那截被夹住，接不到外面的木块
        int tail = (p == j - 1) ? 0 : f(p + 1, j - 1, 0);
        int cand = f(i, p, k + seg_size[j]) + tail;
        if (cand > res) {
            res = cand;
        }
    }
    return res;
}

// 一组数据的最高分
int score(vector<int>& colors) {
    seg_cnt = 0;
    seg_size.clear();
    earlier.clear();
    vector<vector<int> > seen; // 每个颜色已经出现过的段号，递增
    int previous = 0;          // 颜色 ∈ [1,n]，哨兵 0 保证第一块不并进上一段
    for (int t = 0; t < (int)colors.size(); t++) {
        int value = colors[t];
        if (previous == value) { // 与上一块同色：并进当前段
            seg_size[seg_cnt - 1]++;
            continue;
        }
        if ((int)seen.size() <= value) {
            seen.resize(value + 1);
        }
        vector<int> rev;
        for (int q = (int)seen[value].size() - 1; q >= 0; q--) {
            rev.push_back(seen[value][q]);
        }
        earlier.push_back(rev);
        seen[value].push_back(seg_cnt);
        seg_size.push_back(1);
        seg_cnt++;
        previous = value;
    }
    dim = (int)colors.size() + 2;
    memo.assign((seg_cnt + 1) * dim * dim, -1);
    return f(0, seg_cnt - 1, 0);
}

int main() {
    int T;
    if (scanf("%d", &T) != 1) {
        return 0;
    }
    for (int tc = 1; tc <= T; tc++) {
        int n;
        scanf("%d", &n);
        vector<int> colors(n);
        for (int i = 0; i < n; i++) {
            scanf("%d", &colors[i]);
        }
        printf("Case %d: %d\n", tc, score(colors));
    }
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 23:03
# update_at: 2026-10-01 23:20

import sys
from functools import cache

SIZE: list[int] = []                    # SIZE[i]：第 i 个颜色段里有几个木块
EARLIER: list[tuple[int, ...]] = []     # EARLIER[i]：第 i 段前面同色的段号，从近到远严格递减


@cache
def f(i: int, j: int, k: int) -> int:
    """消掉颜色段 i..j 的最高分，其中段 j 那一次消除还会额外带上它右边的 k 个同色木块。

    也就是说，段 j 最终是和 (SIZE[j] + k) 个同色木块一起消掉的。k 只可能由"更右边的段
    被留到最后与 j 合并"产生，因此它一定是若干整段的木块总数。
    读的是模块级的 SIZE / EARLIER，换一组数据前必须先调用 f.cache_clear()。
    """
    if i == j:
        return (SIZE[j] + k) ** 2
    res = f(i, j - 1, 0) + (SIZE[j] + k) ** 2    # 段 j 的这次消除不牵涉 i..j-1 的任何段
    for p in EARLIER[j]:
        if p < i:
            break                                # EARLIER[j] 递减，再往前都越界了
        # 段 j 的这次消除还包含左边的同色段 p：中间那截被 p 和 j 夹住，接不到外面的木块
        tail = 0 if p == j - 1 else f(p + 1, j - 1, 0)
        cand = f(i, p, k + SIZE[j]) + tail       # 段 p 右边因此挂上 SIZE[j] + k 块
        if cand > res:
            res = cand
    return res


def score(colors: list[int]) -> int:
    """一组数据的最高分：先把相邻同色木块压成颜色段，再求 f(0, m-1, 0)。"""
    global SIZE, EARLIER
    size: list[int] = []
    earlier: list[tuple[int, ...]] = []
    seen: dict[int, list[int]] = {}      # 每个颜色已经出现过的段号，递增
    previous = 0                         # 颜色 ∈ [1, n]，哨兵 0 保证第一块不并进上一段
    for value in colors:
        if previous == value:            # 与上一块同色：并进当前段，它俩分开消只会更差
            size[-1] += 1
            continue
        earlier.append(tuple(reversed(seen.get(value, ()))))
        seen.setdefault(value, []).append(len(size))
        size.append(1)
        previous = value
    SIZE, EARLIER = size, earlier
    best = f(0, len(size) - 1, 0)
    f.cache_clear()                      # 缓存是模块级的，不清会让多组数据的内存累加
    return best


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    T = next(data)
    out: list[str] = []
    for tc in range(1, T + 1):
        n = next(data)
        out.append(f"Case {tc}: {score([next(data) for _ in range(n)])}")
    print("\n".join(out))


if __name__ == "__main__":
    solve()

复杂度

时间复杂度：状态是三元组 $(i,j,k)$ ，区间 $O(m^2)$ 个、 $k$ 的可达取值最多 $n$ 种，状态数上界 $O(n^3)$ ；每个状态枚举 $P_j$ 中 $\geqslant i$ 的段，最坏 $O(m)$ 个，因此最坏 $O(n^4)$ ——这正是本题经典三维区间 DP 的阶，没有退化。实际访问量远小于上界：单组 $n = 200$ 、颜色数约 8 的数据只访问约 13 万个状态，均摊每个状态只枚举约 6 个候选段。
空间复杂度： $O(\text{可达状态数})$ 个整数。实现上把 f 放在模块级并读取全局 SIZE/EARLIER，每组数据算完立即 f.cache_clear()；若改用闭包捕获每组数据，上一组的缓存会被函数对象一直持着，多组数据下峰值内存会成倍上涨。

总结

本题有两个必须想清楚的点。

一是压缩。 相邻同色木块一定一起删，把 $n$ 个木块压成 $m$ 个颜色段，既是剪枝也是后面状态定义的前提。

二是状态的第三维。 只记区间 $[i,j]$ 是不够的，因为段 $j$ 右边可能粘着一批同色木块等着和它一起消。多加一维 $k$ 记“右边还要接上多少块”，就足以描述所有对未来有影响的信息。而 $k$ 的来源唯一（只可能是“右边某一段被完整留到现在与 $j$ 合并”），所以 $k$ 的取值只能是若干段长度之和，可达状态数明显少于“所有整数 $k$ ”的上界。

转移时注意一件事：段 $j$ 若跨过中间某截去和段 $p$ 合并，中间那截必须独立求解（ $k = 0$ ），因为它被 $p$ 挡住，接不到外面的木块。这一条写错会让答案偏大。

图示解析

这张图串起从输入到答案的主线：

text

1
2
3
4
5
6
7输入：n 个木块
`- 相邻同色必然一起消 -> 压成 m 个颜色段 s[0..m-1]
   `- 一次删除 = 若干个整段的并集，中间的段已被删空
      `- 状态 f(i, j, k)：段 i..j 的最优分，段 j 那一次消除还会带上右边 k 块同色木块
         |- 段 j 单独消         -> f(i, j-1, 0) + (s_j + k)^2
         `- 段 j 去和同色的段 p 合并 -> f(i, p, k+s_j) + f(p+1, j-1, 0)
            `- 中间那截两头被堵，k 只能取 0

接下来把样例 $f(0,3,0) = 29$ 的决策展开成一棵递归树。每个结点是一个状态，缩进的一层是它依赖的子状态，叶子就是实际拿到的分数：

text

1
2
3
4
5`- f(0,3,0) = 29        段3 的那次消除拉上左边的同色段0
   |- f(0,0,1) = 4       ① 段0 的右边接上段3：1 + 1 = 2 块 -> 2² = 4
   `- f(1,2,0) = 25      ② 中间被夹住的那截（k = 0）
      |- 段2 不再牵涉区间内别的段     3 块 -> 3² = 9
      `- f(1,1,0) = 16               段1：4 块 -> 4² = 16

读图时关注三点：状态名里的两个数字是它管辖的段区间，第三个是段 $j$ 右边还要接上的同色块数；转移二会同时产生两个子问题，其中被夹在中间的那个一定带着 $k = 0$ ；三个叶子上的分数 $4 + 9 + 16$ 加起来正好是 $29$ 。