1. 题目理解

我们有一个数组，每次操作可以选定一个不包含颜色 $k$ 的子段，然后将整个子段染成颜色 $k$。目标是让整个数组变成单一颜色，求最小操作次数。

数据规模：$n \le 100$，$x \le n$，$\sum n \le 500$。允许 $O(n^4)$ 的 DP。

2. 关键观察

一次操作的效果是将一个子段统一染成某颜色，且该颜色之前不在子段中出现。这暗示我们可以将原问题划分为子区间上的子问题。

定义两种状态：

• $dp1[l][r][c]$：将区间 $[l, r]$ 全部染成颜色 $c$ 所需的最少操作次数（注意：这里的 $l, r$ 是经过“压缩”后的下标，即去掉了区间两端已经是颜色 $c$ 的部分，因为两端已是 $c$ 的话无需操作）。
• $dp2[l][r][c]$：将区间 $[l, r]$ 变成不包含颜色 $c$ 的任意状态（即最终颜色不是 $c$）所需的最少操作次数。

标程中通过预处理 nxtx、prvx 等数组来快速跳过已经是某颜色的元素，从而将区间压缩到真正需要处理的范围。

3. 预处理数组

• nxtx[i][c]：从下标 $i$ 开始（包括 $i$）向右第一个颜色等于 $c$ 的位置。
• prvx[i][c]：从下标 $i$ 开始向左第一个颜色等于 $c$ 的位置。
• nxtnx[i][c]：从 $i$ 开始向右第一个颜色不等于 $c$ 的位置。
• prvnx[i][c]：从 $i$ 开始向左第一个颜色不等于 $c$ 的位置。

这些预处理允许我们在 DP 时直接跳过区间两端已经是目标颜色（或不是目标颜色）的元素，缩小状态空间。

4. DP 转移

$dp1[l][r][c]$：将区间染成颜色 $c$

首先用预处理数组将 $l$ 跳到第一个不为 $c$ 的位置，$r$ 跳到最后一个不为 $c$ 的位置。若 $l > r$，说明区间已经全是 $c$，返回 $0$。

转移有两种选择：

1. 直接染色：先用若干操作将区间变成不包含 $c$ 的状态（即 $dp2[l][r][c]$），然后一次操作将整个区间染成 $c$，总次数 $dp2[l][r][c] + 1$。
2. 分治染色：将区间分成两段 $[l, i]$ 和 $[i+1, r]$，分别染成 $c$，取最小次数之和。

$$dp1[l][r][c] = \min\left(dp2[l][r][c] + 1, \min_{i=l}^{r-1} \{dp1[l][i][c] + dp1[i+1][r][c]\}\right) $$

$dp2[l][r][c]$：将区间变成不含 $c$ 的状态

同样先压缩 $l$ 到第一个等于 $c$ 的位置，$r$ 到最后一个等于 $c$ 的位置。若 $l > r$，说明区间内没有 $c$，返回 $0$。

转移有两种：

1. 分治：将区间分成两部分分别处理，求和。
2. 先染成其他颜色 $y$：选择一种其他颜色 $y \ne c$，将整个区间染成 $y$（即 $dp1[l][r][y]$），这样区间自然不再含 $c$。

$$dp2[l][r][c] = \min\left(\min_{i=l}^{r-1} \{dp2[l][i][c] + dp2[i+1][r][c]\}, \min_{y \ne c} dp1[l][r][y]\right) $$

最终答案是对所有颜色 $c$，取 $dp1[0][n-1][c]$ 的最小值。

5. 复杂度分析

• 状态数：$O(n^2 \cdot x)$，每个状态转移需要 $O(n)$ 或 $O(x)$ 时间，总复杂度 $O(n^3 x)$ 或 $O(n^2 x^2)$。
• 由于 $n \le 100, x \le n$，最大计算量约为 $10^6 \sim 10^7$ 级别，在 $3$ 秒内完全可行。
• 使用记忆化搜索（标程中的递归写法）实现 DP。

6. 代码（附注释）

#include <bits/stdc++.h>
using namespace std;

const int N = 111;

int n, k;
int a[N];
int nxtx[N][N], prvx[N][N];    // 下一个/上一个颜色等于 x 的位置
int nxtnx[N][N], prvnx[N][N];  // 下一个/上一个颜色不等于 x 的位置
int dp1[N][N][N], dp2[N][N][N];

int calc2(int l, int r, int x);

int calc1(int l, int r, int x) {
    // 压缩区间：跳过两端已经是颜色 x 的元素
    l = nxtnx[l][x], r = prvnx[r][x];
    if (l > r) return 0;
    if (dp1[l][r][x] != -1) return dp1[l][r][x];
    
    // 选项1：先变成不含 x 的状态，再一次染色
    dp1[l][r][x] = calc2(l, r, x) + 1;
    // 选项2：分两段分别染色
    for (int i = l; i < r; ++i)
        dp1[l][r][x] = min(dp1[l][r][x], calc1(l, i, x) + calc1(i + 1, r, x));
    return dp1[l][r][x];
}

int calc2(int l, int r, int x) {
    // 压缩区间：跳过两端不等于颜色 x 的元素（即定位到含有 x 的部分）
    l = nxtx[l][x], r = prvx[r][x];
    if (l > r) return 0;
    if (dp2[l][r][x] != -1) return dp2[l][r][x];
    
    dp2[l][r][x] = n; // 初始化为较大值
    // 选项1：分两段分别处理
    for (int i = l; i < r; ++i)
        dp2[l][r][x] = min(dp2[l][r][x], calc2(l, i, x) + calc2(i + 1, r, x));
    // 选项2：直接染成另一种颜色 y
    for (int y = 0; y < k; ++y)
        if (x != y)
            dp2[l][r][x] = min(dp2[l][r][x], calc1(l, r, y));
    return dp2[l][r][x];
}

void solve() {
    cin >> n >> k;
    for (int i = 0; i < n; ++i) cin >> a[i], --a[i];  // 转为0-based颜色
    
    // 初始化前驱数组
    for (int x = 0; x < k; ++x) prvx[0][x] = prvnx[0][x] = -1;
    for (int i = 0; i < n; ++i) {
        prvx[i][a[i]] = i;
        for (int x = 0; x < k; ++x) prvx[i + 1][x] = prvx[i][x];
        for (int x = 0; x < k; ++x) if (x != a[i]) prvnx[i][x] = i;
        for (int x = 0; x < k; ++x) prvnx[i + 1][x] = prvnx[i][x];
    }
    
    // 初始化后继数组
    for (int x = 0; x < k; ++x) nxtx[n][x] = nxtnx[n][x] = n;
    for (int i = n - 1; i >= 0; --i) {
        for (int x = 0; x < k; ++x) nxtx[i][x] = nxtx[i + 1][x];
        nxtx[i][a[i]] = i;
        for (int x = 0; x < k; ++x) nxtnx[i][x] = nxtnx[i + 1][x];
        for (int x = 0; x < k; ++x) if (x != a[i]) nxtnx[i][x] = i;
    }
    
    memset(dp1, -1, sizeof(dp1));
    memset(dp2, -1, sizeof(dp2));
    
    int ans = n;
    for (int x = 0; x < k; ++x)
        ans = min(ans, calc1(0, n - 1, x));
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

7. 总结

本题是一道典型的区间 DP 题目，难点在于设计合适的状态和转移。通过引入 $dp1$（染成特定颜色）和 $dp2$（避免特定颜色）两个互补状态，并利用预处理数组压缩区间边界，使得 DP 能够高效进行。这种方法同样适用于其他具有“染色”或“覆盖”性质的区间操作问题。