这题挺有意思
首先我们有一些显然的观察：每本书最多移动一次，且每种颜色有下面三种情况：
- 全部移到最后了
- 全部没移，其中间的都被移走了
- 有一个后缀没移，且除了这个后缀的所有颜色移到了这个后缀的后面。
从后往前 dp 即可，另外如果把记删除最少改为保留最多会更好写。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
// typedef __int128 i128;
typedef pair<int, int> pii;
const int N = 5e5 + 10, mod = 998244353;
template<typename T>
void dbg(const T &t) { cout << t << endl; }
template<typename Type, typename... Types>
void dbg(const Type& arg, const Types&... args) {cout << arg << ' ';dbg(args...);
}
namespace Loop1st {
int n, a[N], f[N], l[N], r[N], cnt[N];
void main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];if (!l[a[i]]) l[a[i]] = i;r[a[i]] = i;}for (int i = n; i; i--) {cnt[a[i]]++;f[i] = f[i + 1];if (l[a[i]] == i) f[i] = max(f[i], f[r[a[i]] + 1] + cnt[a[i]]);else f[i] = max(f[i], cnt[a[i]]);}cout << n - f[1] << '\n';
}}
int main() {// freopen("data.in", "r", stdin);// freopen("data.out", "w", stdout);ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int T = 1;// cin >> T;while (T--) Loop1st::main();return 0;
}