祖玛

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

思路

一次操作删掉的是什么。 操作删掉的是「当前序列」里的一段回文，换成原序列的下标来看：它删掉一组下标 $i_1<i_2<\cdots<i_m$，这组下标的颜色按顺序读是回文（$c_{i_1}=c_{i_m}$，$c_{i_2}=c_{i_{m-1}}$，依此类推），并且每对相邻下标 $i_j,i_{j+1}$ 之间的宝石在此刻都已经删干净了。

由此可以看出整个解的分层结构：任取两次操作，它们删掉的下标集合不会交叉——若 $A$ 先于 $B$ 执行，$B$ 执行时 $B$ 的下标在序列里连续，$A$ 的下标不可能夹在 $B$ 的最小、最大下标之间。所以每个操作都「套」在另一个操作的某个空档里，或者说落在互不相交的区间中，于是可以按区间递归地描述，适合区间 DP。

状态。 $dp[l][r]$ 表示把原序列区间 $[l,r]$ 内的宝石全部删光所需的最少操作次数，$dp[l][l]=1$。

转移一：拆成两段独立删。 左右两段各自删光，彼此不干扰：

$dp[l][r]\le\min_{l\le k<r}\bigl(dp[l][k]+dp[k+1][r]\bigr).$

转移二：两端同色时可以并进同一次操作。 设 $c_l=c_r$，取 $[l+1,r-1]$ 的任一最优方案，考察它的最后一次操作，设它删掉的回文是 $p_1<\cdots<p_m$。这次操作执行时，$[l+1,r-1]$ 里除这 $m$ 颗宝石外都已删空，所以 $l$ 紧挨着 $p_1$、$r$ 紧挨着 $p_m$；又 $c_l=c_r$ 且 $p_1,\dots,p_m$ 是回文，故 $l,p_1,\dots,p_m,r$ 仍然是回文，把这最后一次操作换成删除它们即可，操作数不变。于是

$dp[l][r]\le dp[l+1][r-1]\qquad(c_l=c_r).$

注意这里代价是 $+0$ 而不是 $+1$：中间那段的最后一次操作被吸收进了含两端的那一次操作。$r=l+1$（中间为空）要单独取 $dp[l][l+1]=1$。

容易写错的一版是 $dp[l+1][r-1]+1$，即「先把中间删空，再单独删两端」，它漏掉了「整个区间本身就是回文」的情形：$2,3,2$ 一次就能删完，而 $+1$ 的写法得到的是 $2$。

转移的完备性。 任取 $[l,r]$ 的一个最优方案，设删掉 $l$ 的那次操作删掉的下标是 $l=i_1<i_2<\cdots<i_m$，它内部的空档都更早被删空，$i_m$ 右侧的部分记作 $T$。

• $m=1$：该操作只涉及 $l$，费用为 $1+dp[l+1][r]$，转移一取 $k=l$ 即可。
• $m\ge2$：先用转移一在 $i_m$ 处拆开，$dp[l][r]\le dp[l][i_m]+dp[i_m+1][r]$，后一项正是 $T$ 的费用。对 $[l,i_m]$ 反复使用转移二剥掉最外层的一对：由 $c_{i_1}=c_{i_m}$ 有 $dp[i_1][i_m]\le dp[i_1+1][i_m-1]$，而区间 $[i_1+1,i_m-1]$ 里的 $G_0=(i_1,i_2)$、$G_{m-1}=(i_{m-1},i_m)$ 两段空档可以由转移一单独结算，剩下的 $i_2,\dots,i_{m-1}$ 是同一个结构、长度减二的问题，归纳下去即可。剥到最内层时，奇数长度的核心是单颗宝石（恰好对应外层那次操作的 $1$ 次），偶数长度的核心是一对同色宝石（转移二的 $+0$ 把它们并进同一次操作）。因此总费用不超过原方案的 $1+\sum dp(G_j)$，两个转移足以覆盖所有情形。

也就是说，$[l,r]$ 的最优解中，删掉 $l$ 的那次操作要么只含 $l$，要么从 $l$ 一路延伸到某个 $i_m$，而 $i_m$ 之后与之前都可以拆成更小的区间问题，这正是上面两个转移所枚举的。

检验。 样例 $1,2,3,2,1,4$ 中前五颗构成回文，先删它们再删最后一颗，代价 $2$，与样例一致；而整个 $[l,r]$ 是回文时（如 $2,3,2$）答案为 $1$，正是转移二 $+0$ 的效果。

复杂度

状态数 $O(n^2)$，每个状态枚举 $O(n)$ 个切点，时间 $O(n^3)$（$n=500$ 时约 $500^3/6\approx2\times10^7$ 次运算），空间 $O(n^2)$。

仓颉实现

二维表按一维数组存储，下标为 $l\cdot(n+1)+r$。按区间长度从小到大递推：先处理两端同色的合并，再枚举切点。

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

main() {
    let reader = getStdIn()
    let n = Int64.parse(reader.readln().getOrThrow())
    let c = reader.readln().getOrThrow().split(" ", removeEmpty: true).map({ p: String => Int64.parse(p) })
    let INF: Int64 = 1000000000
    let w = n + 1
    let dp = Array<Int64>(w * w, { _ => 0 })
    for (i in 0..n) {
        dp[i * w + i] = 1
    }
    for (len in 2..=n) {
        for (l in 0..=(n - len)) {
            let r = l + len - 1
            var best: Int64 = INF
            if (c[l] == c[r]) {
                if (len == 2) {
                    best = 1
                } else {
                    best = dp[(l + 1) * w + (r - 1)]
                }
            }
            let base = l * w
            for (k in l..r) {
                let v = dp[base + k] + dp[(k + 1) * w + r]
                if (v < best) {
                    best = v
                }
            }
            dp[base + r] = best
        }
    }
    println(dp[n - 1])
}