CF1481E Sorting Books

· · 题解

首先有个最简单的观察，被移动的书在序列右侧可以随便排列。

由于和序列后面关联性很强，所以考虑倒序 DP。

设 f_i 表示从 i 到 n 能留下来的最多的书，同时要满足一个条件，即对于某一颜色而言，若左侧还有未被考虑的书，那么已经被考虑的那些书要么都是被移动过的，要么 满足他们右侧没有不移动的书，也就是前面的同色书移动后可以接到它们后面。

转移式很简单，不选直接继承。选的话由于要满足条件，所以如果当前的书是它的同色书中最左侧的一本，那么可以加上右端点后一个位置的 DP 值，如果不是，由于要满足条件，所以除同色书其余的都要移动，转移代码如下。


cnt[col[i]] ++ ;
f[i] = f[i + 1];
f[i] = max(f[i], cnt[col[i]]);
if (i == Left[col[i]])
    f[i] = max(f[i], cnt[w[i]] + f[Right[col[i]] + 1]);

答案即为 n - f_1。