题解：CF1481E Sorting Books

include13_fAKe · 2025-10-18 10:30:55 · 题解

如此费解的题目，我拖了半年才终于搞了出来……

以下设 dp_i 代表把 [i,n] 区间排列整齐的最多可保留的书的数目。通过暴力搜索和肉眼观察可得：每一本书最多移动一次！

转移分为 3 类：

• 移动这本书：dp_i=dp_{i+1}。
• 将所有某种颜色的书之间的其他颜色的书移走：设这个颜色的书的范围为 [l,r]，出现次数为 cnt（全文余同），转移即为 dp_l = dp_{r+1}+cnt。
• 对于任意一堆从后往前（要求是后缀和）的相同颜色的书，可以将其全部置于末尾，之后运用单纯的移动，将所有同色书放在一起：dp_{i}=cnt。（cnt 需要动态更新）

时间复杂度 O(n)。

#include<bits/stdc++.h>
#define int long long
#define mp(a,b) make_pair(a,b)
using namespace std;

inline int read(){
    int a=0,b=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-')  b=-1;
        c=getchar();
    }
    while(isdigit(c)){
        a=(a<<1)+(a<<3)+(c-'0');
        c=getchar();
    }
    return a*b;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>=10)   write(x/10);
    putchar(x%10+48); 
}
inline void write1(int x){
    write(x),putchar(' ');
}
inline void write2(int x){
    write(x),putchar('\n');
}
int n;
int a[5*114514];
int l[5*114514],r[5*114514];
int dp[5*114514];   //倒序 dp  

int cnt[5*114514];
#undef int
int main(){
    #define int long long
    n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        if(!l[a[i]])    l[a[i]]=i;
        r[a[i]]=i;
    } 
    for(int i=n;i>=1;i--){
        //枚举的是有多少个元素可以不动？
        dp[i]=dp[i+1];  //代表直接移走？ 
        cnt[a[i]]++;
        dp[i]=max(dp[i],cnt[a[i]]);
        if(l[a[i]]==i){
            dp[i]=max(dp[i],dp[r[a[i]]+1]+cnt[a[i]]);
        } 
//      cout<<'!'<<dp[i]<<endl;
    }
    write2(n-dp[1]);
    return 0;
} //一定要挽回罗琪钧的遗憾啊，一定会挽回罗琪钧的遗憾的！