核心思路

• 对于第 $k$ 个块，原本两位记为$a, b$。若把该块改成 $[v, v]$，代价是 $\text{cost}_k(v)$=$\mathbf{1}[a\ne v]$+$\mathbf{1}[b\ne v]$=$2$-$\mathbf{1}[a=v]$-$\mathbf{1}[b=v]$ 它只可能是 $0,1,2$ 三种情况： 若 $a=b=v$ 则代价为 $0$；若 $v\in{a,b}$ 且 $a\ne b$ 则代价为 $1$；否则为 $2$。

• 相邻块必须选择不同的 $v$。因此做一维按块推进、按末尾选值的动态规划：

  • 设 $m=\frac{n}{2}$ 为块数，数字候选为 $v\in{0,\dots,9}$。