codeforces E. Sorting Books

· · 个人记录

E. Sorting Books

给你 n 本书的颜色 ，每次可以将任意位置的书移动到末尾 ，最后让相同颜色的书都相连，求最小的步数 .

我们可以发现 ，最优解一定是某种颜色因为移动或抽出中间的其他颜色使其相连，贪心发现某个颜色连成一片有一下两种方式 ： 1.直接将所有的相同颜色移动到队伍末尾 2. 将某个颜色前缀的某些书移动到队伍末尾再将完成后中间其他颜色移动于末尾 。正难则反，让我们求最少的移动量，我们可以先求最大的保留量，显然两个颜色如果都要保留，则它们不可相交(最左，最右)+个数为权值 。因此我们可以先将所有区间处理出然后 dp 就好了 。但是发现只是用 (最左，最右) 只能照顾到第一种转移方式 ，对于第二种转移我们将每个颜色后缀变成一个区间 i->n，权值为后缀相同颜色个数 .因为我们要将某个颜色移动到末尾新形成的区间中部所有其他颜色的都要移动走。最后统一 dp 就好了 。 


#include<bits/stdc++.h> 

using namespace std;

const int maxn=2e6+10;
int a[maxn],n,f[maxn],id[maxn],num,ans,N,sum[maxn];

struct node
{
    int l,r,w;
}t[maxn];

bool cmp(node a,node b) {
    return a.l<b.l;
}

int main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i) {
        scanf("%d",&a[i]);if(!id[a[i]]) id[a[i]]=++num;if(!t[id[a[i]]].l) t[id[a[i]]].l=i;t[id[a[i]]].r=i;t[id[a[i]]].w++;
    }
    int now=1;
    for(int i=n;i;i--) {
        sum[a[i]]++;
        t[++num].l=i;t[num].r=n;t[num].w=sum[a[i]];
    }
    sort(t+1,t+num+1,cmp);
    for(int i=1;i<=n;++i) {
        while(t[now].l==i) {
            f[t[now].r+1]=max(f[t[now].r+1],f[i]+t[now].w);now++;
        }
        f[i+1]=max(f[i+1],f[i]);
    }
    cout<<n-f[n+1]<<"\n";
    return 0;
}

/*
10
9 8 7 3 6 3 10 9 9 3  

*/