题解

思路

最小移动数等于 $n$ 减去最多能原地保留的书数。未移动的书保持原相对顺序，移动的书可以按操作顺序在末尾任意排列。

设未移动部分依次出现若干颜色块。除最后一个颜色外，之前每个颜色的所有书都必须原地保留；否则该颜色被移动的书只能出现在所有未移动书之后，会与原来的颜色块分离。最后一个颜色可以只保留当前边界之后的出现，移动的同色书紧接着放到末尾即可。

因此，完整保留的颜色 $c$ 对应区间 $[first_c,last_c]$，其权值为出现次数 $cnt_c$。多个完整颜色必须按互不相交的出现区间排列。这是带权区间选择。

做法

令 $dp_i$ 为最后出现位置不超过 $i$ 的完整颜色链最多能保留多少本书。扫描到颜色 $c$ 的最后出现位置时，用

更新当前值。

再从右向左统计每个后缀中某种颜色的最高频次 $suf_i$。枚举完整颜色链结束边界 $i$，最多保留 $dp_i+suf_{i+1}$ 本；其中后半项作为最后一个可部分保留的颜色。取最大值并用 $n$ 减去它。

子任务 1 可枚举所有未移动书的子集并检查能否补成美观序列；子任务 2 可按颜色最后位置排序，显式枚举上一个不相交颜色做二次区间 DP。

复杂度

时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。