E. Sorting Books
首先每本书都移动，移动次数是n能够满足题意。如果某些书不用移动，说明把隔开他们中间的书全部抽走后自然成组。
对于每本书全部移动的情况，显然我们可以选择一种颜色的书全部不案，移动别的书，抽走隔开的书后那么他们就会自然成组。
如果存在选择2种书不动的方案，不难知道该两种书出现的区间一定不能相交，因为他们都是自然成组的，如果相交会互相隔断。同理选择3种书不动的方案也一样。
预处理每种书出现的区间
l
i
,
r
i
l_i,r_i
li,ri
状态表示：
f
i
f_i
fi表示区间
[
i
,
n
]
[i,n]
[i,n]中不需要移动书的最大数量。
状态转移：
倒着转移
n
→
i
n\to i
n→i
对于第
i
i
i本书，我们可以移动此书，那么
f
i
=
f
i
+
1
f_i=f_{i+1}
fi=fi+1
如果不动此书，那么与此书颜色相同的书也应该不动
如果
l
a
i
=
i
l_{a_i}=i
lai=i，说明
a
i
a_i
ai颜色的书整个区间出现完即可以合并
f
i
=
f
r
a
i
+
1
+
c
n
t
a
i
f_i=f_{r_{a_i}+1}+cnt_{a_i}
fi=frai+1+cntai，选择多种书（不相交）不动的方案
否则
f
i
=
c
u
r
a
i
f_i=cur_{a_i}
fi=curai，只能选择一种书不动
#define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
#pragma GCC optimize(2)
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
constexpr int N=500010;
int a[N],f[N],cur[N],n;
int l[N],r[N];
int main()
{
IO;
cin>>n;
memset(f,0,(n+1)*sizeof(int));
memset(l,0x3f,(n+1)*sizeof(int));
memset(r,-1,(n+1)*sizeof(int));
for(int i=1;i<=n;i++)
{
cin>>a[i];
l[a[i]]=min(l[a[i]],i);
r[a[i]]=max(r[a[i]],i);
}
for(int i=n;i;i--)
{
cur[a[i]]++;
// a[i] 移动
f[i]=f[i+1];
// a[i] 不动
if(i==l[a[i]])
f[i]=max(f[i],cur[a[i]]+f[r[a[i]]+1]);
else
f[i]=max(f[i],cur[a[i]]);
}
cout<<n-f[1]<<'\n';
return 0;
}
除夕快乐！