比赛链接

给定一个长度为 $n$ 的序列 $\{a\}$，每次操作可以任取一个位置并将该位置的数移到序列末尾。

问最少需要多少次操作才能使序列中所有大小相同的数相邻。

显然只需要在序列中选定一些位置，然后按特定顺序将他们移除就可以完成任务。定义 $\text{dp}(i)$ 表示不移动序列 $[i,n]$ 的位置的个数。

维护每个值 $v$ 的最靠左出现的位置 $l_v$，最靠右出现的位置 $r_v$，动态维护 $[i,n]$ 中出现的次数 $c_v$。

于是如果选择保留位置 $i$，若 $i=l_{a_i}$，则需要移除 $[i,r_{a_i}]$ 中所有不等于 $a_i$ 的位置，即 $\text{dp}(i)=r_{a_i}-l_{a_i}+1-c_{a_i}+\text{dp}(r_{a_i}+1)$。

若 $i\neq l_{a_i}$，则需要移除 $[i,n]$ 中所有不等于 $a_i$ 的位置，