洪水染色

数据规模：$1 \le n \le 5000$，$1 \le c_i \le 5000$。

思路

先合并连通块。 一次操作改变的是「包含起点的整个连通块」，永远不会把连在一起的两个同色方格拆开，所以相邻同色的方格可以视为一个整体。把输入压成 $m$ 个颜色交替的块 $c_1,c_2,\ldots,c_m$（$c_i \ne c_{i+1}$），答案不变。

一次操作等价于区间扩张。 设起点在第 $p$ 个块内，并记「当前包含起点的块」覆盖的块下标区间为 $[l,r]$，初始 $l=r=p$。由于它始终是一段连续区间，一次操作把它整体改成颜色 $x$ 时只有下面几种结果：

• $x=c_{l-1}$：左侧相邻块被吞并，区间变成 $[l-1,r]$；
• $x=c_{r+1}$：右侧相邻块被吞并，区间变成 $[l,r+1]$；
• $c_{l-1}=c_{r+1}=x$：两侧同色，一次改色同时吞并两格，区间变成 $[l-1,r+1]$；
• 其余情况区间没有变化，是纯粹的空耗，不会出现在最优方案里。

所以每次操作要么让区间向一侧长一格，要么在左右两个相邻块同色时长两格。目标是把区间扩张到 $[1,m]$，且起点可以任选，于是问题化为：用最少的扩张次数把 $[1,m]$ 吞成一个块。

状态与转移。 定义 $dp[l][r]$ 为把块 $l..r$ 合并成一个块所需的最少操作数，起点在 $l..r$ 内且只允许吞并 $l..r$ 内的块，边界 $dp[l][l]=0$。

考虑让区间变成 $[l,r]$ 的最后一次操作，它只有三种可能：

• 只吞了 $l$：此前是 $[l+1,r]$ 且已合成一块，代价 $dp[l+1][r]+1$；
• 只吞了 $r$：代价 $dp[l][r-1]+1$；
• 同时吞了 $l$ 与 $r$：一次改色要同时匹配两侧颜色，必须 $c_l=c_r$，此前区间是 $[l+1,r-1]$，代价 $dp[l+1][r-1]+1$。

于是

当 $c_l=c_r$ 时再与 $dp[l+1][r-1]+1$ 取较小值。答案即 $dp[1][m]$。

为什么同色两端能省一步。 两端颜色相同时，把它们中间的部分先合成一块，再一次改色就能同时吃掉左右两个端点块，把原本要分开做的两次吞并合并成一次。这也是样例 $1,2,1$ 的答案：中间块改成 $1$，一步同时并掉左右两个 $1$。

为什么拆成「最后一步」不重不漏。 任何合法方案都对应区间从中心向两侧逐格扩张的过程，把它的最后一次扩张删掉，剩下的仍是一个合法方案，且中间状态正是 $[l+1,r]$、$[l,r-1]$ 或 $[l+1,r-1]$ 三者之一；反过来，这三种子方案各自都能补上那最后一步得到 $[l,r]$。归纳即可。

滚动数组。 $dp[l][r]$ 只依赖长度为 $len-1$ 与 $len-2$ 的两层，按区间长度从小到大递推时保留这两层即可，空间降到 $O(m)$。长度为 $0$ 的空区间取值 $0$，正好对应 $c_l=c_r$ 且中间为空时一步吞掉两个块（此时 $l+1=r$，答案为 $1$）。

小例子核对。 $1,2,3,2,1$：$c_1=c_5$，取 $dp[2][4]+1=1+1=2$；$1,2,1,2$：两端不同，$\min(dp[2][4],dp[1][3])+1=1+1=2$；全同色压缩后 $m=1$，答案为 $0$。

复杂度

共 $O(m^2)$ 个状态、每个状态常数次转移，时间 $O(m^2)$；滚动数组只保留两层，空间 $O(m)$。其中 $m \le n$ 是压缩后的块数。

仓颉实现

import std.env.*
import std.convert.*

main() {
    let reader = getStdIn()
    let n = Int64.parse(reader.readln().getOrThrow())
    let raw = reader.readln().getOrThrow().split(" ", removeEmpty: true).map({ p: String => Int64.parse(p) })
    let blk = Array<Int64>(n, { _ => 0 })
    var m: Int64 = 0
    for (i in 0..n) {
        if (m == 0 || blk[m - 1] != raw[i]) {
            blk[m] = raw[i]
            m += 1
        }
    }
    if (m == 1) {
        println(0)
    } else {
        var prev1 = Array<Int64>(m, { _ => 0 })
        var prev2 = Array<Int64>(m, { _ => 0 })
        var cur = Array<Int64>(m, { _ => 0 })
        for (len in 2..=m) {
            for (l in 0..=(m - len)) {
                var best = prev1[l]
                if (prev1[l + 1] < best) {
                    best = prev1[l + 1]
                }
                best += 1
                if (blk[l] == blk[l + len - 1]) {
                    let v = prev2[l + 1] + 1
                    if (v < best) {
                        best = v
                    }
                }
                cur[l] = best
            }
            let tmp = prev2
            prev2 = prev1
            prev1 = cur
            cur = tmp
        }
        println(prev1[0])
    }
}