染色

[[IntervalDP|IntervalDP]]

You are given an array $A$ of length $N$ consisting of non-negative integers.

You have another array $c$ of the same length. Initially, $c_{i}=0$ for all $1 \leqslant i \leqslant N$.

You can perform the following operation any number of times:

• Choose a non-negative integer $x$ and a subarray $[l, r]$, then set $c_{i} := x$ for all $l \le i \le r$.

Find the minimum number of operations required to transform the array $c$ into the target array $A$.

Note that the target array $A$ may contain zeros.

$1 \leqslant N \leqslant 500$
$0 \leqslant A_{i} \leqslant N$

给定数组 $A$。
初始有一个全为 0 的数组，每次任选一个非负整数 $x$，任选一个区间 $[l,r]$，把区间 $[l,r]$ 都变成 $x$，最少需要多少次得到目标数组？ 目标数组可能包含 0。

第一步：不考虑 0，区间 DP

• 初始状态：$f_{i,i} = 1$
• $f_{i,j} = \min_{i \le k < j} \{f_{i,k} + f_{k+1,j} \}$
• 如果 $A[i] = A[j]$，$f_{i,j} = f_{i+1,j}$

第二步：考虑 0，线性 DP

• $g_i$ 表示将初始全 0 数组的前缀 $[1 \dots i]$ 变为目标数组 $A[1 \dots i]$ 的最少操作次数。
• 初始状态：$g_0 = 0$
• 如果 $A[i] = 0$ $g_i = g_{i-1}$
• $g_i = \min_{0 \le k < i} \{g_k + f_{k+1,i} \}$
• 最终答案：$g_n$