\(* \text{Defficult:} \color{Red}{2500}\)
一道很有 AT 风格的 DP。
Description
有 \(n\) 本书，每本书有一个颜色，每次操作可以将一本书移动到最右。
求问使所有相同颜色的书相邻的最小移动次数。
\(n \le 5 \cdot 10^5\)
Solution
首先可以想到，最大的移动次数不会超过 \(n\)，且每本书的移动次数不会超过一次。
因为显然，所有书按照颜色排序然后分别移动即可。
反向考虑，设法求出不用移动的书的最大值。
对于每种颜色的数，记录其最左边出现的位置 \(l_i\)，和最右边出现的位置 \(r_i\)。
设 \(f_i\) 表示使位置在范围 \([i,n]\) 之内的书按照要求排列的最大不移动的书的数量。
考虑如何转移：
首先，所有情况下的 \(i\)，都可以选择移动，使之与其他同颜色的书相邻，即 \(f_i =f_{i+1}\)。
转移的过程中，记录此时每种书的出现次数 \(cnt_i\)。
剩下的转移要分情况讨论。
- \(i = l_{a_i}\)
此时可以选择不移动所有颜色为 \(a_i\) 的书，有转移 \(f_{i} = cnt_{a_i} + f_{r_{a_i} +1}\)。
- \(i \ne l_i\)
跟上面一样，考虑颜色为 \(a_i\) 的书不移动。
此时的转移是 \(f_i = cnt_{a_i}\)。
比如考虑 \([1,2,2,1,1,3]\)，当前 \(i=4\) 的情况。
如果选择上述转移，实际上的操作是：
\([1,2,2,1,1,3] \implies [2,2,1,1,3,1] \implies [2,2,1,1,1,3]\)，操作次数为 \(2\)，等于 \(cnt_{a_i}\)。
总结一下，状态转移方程式是：
\[f_i = \max \begin{cases}f_{i+1}\\cnt_{a_i}&i \ne l_{a_i}\\f_{r_{a_i}+1}&i=l_{a_i}\end{cases} \]最后的答案就是 \(n-f_1\)。
时间复杂度：\(O(n)\)。
code
#include <bits/stdc++.h>
using namespace std;
#define L(i,j,k) for(int (i)=(j);i<=(k);(i)++)
#define R(i,j,k) for(int (i)=(j);i>=(k);(i)--)
#define FST ios::sync_with_stdio(0);cin.tie(0);
const int N=2e6+100;
int n,a[N],l[N],r[N],cnt[N],f[N];
signed main(){
FST;cin>>n;L(i,1,n) cin>>a[i],r[a[i]]=i;
L(i,1,n) if(!l[a[i]]) l[a[i]]=i;
R(i,n,1){
cnt[a[i]]++;if(i==l[a[i]])
f[i]=max(cnt[a[i]]+f[r[a[i]]+1],f[i+1]);
else f[i]=max(f[i+1],cnt[a[i]]);
}cout<<n-f[1];
}//CSP-S 2022 RP++