CF1481E Sorting Books

题目链接:https://codeforces.com/problemset/problem/1481/E

题目描述

你现在要整理书架上的 n 本书,每本书有一个颜色 a_i ,当每种颜色的书都摆在一起时书架上便整齐了,你每次可以将一本书放到序列最右端,问使书架上整齐的最小操作数。

n\leq 5\times 10^5a_i\le n

Solution

首先考虑一个区间中如果有 x 种颜色相互交叉,( 如 1,2,3,\dots,x,1,2,3,\dots,x ) ,那我们最多保留 1 种颜色,要操作 x-1 种颜色。

并且若第 i 种颜色的书有 x 种,那么操作 x 次必然能将他们调整在一起。那么其实操作 n 次也必然能将使书架整齐。

我们考虑贪心,试着调整那些数量较少就能整齐的书,从而使得数量较多的书自然而然地排列整齐。但是情况非常复杂,找不到一个统一的结论,所以考虑 DP

由于前文说到 “一个区间中,保留的颜色可能比操作的颜色少很多(最多保留 1 种颜色)“ ,于是我们可能联想到维护一个状态,为不需要移动书的最大数量。

于是我们定义 dp_i 表示 从 i 到 n 不需要移动书的最大数量 ,考虑转移:

我们先定义 L_{a[i]} 为第 a[i] 种颜色的左端点, R_{a[i]} 表示第 a[i] 种颜色的右端点。cnt[a[i]] 表示从 ina[i] 的数量 cnt[a[i]]

① 如果当前位置 pos 是这个颜色的左端点(即 L[a[pos]]=pos

那么我们可以考虑将 [L_{a[pos]} , R_{a[pos]}] 区间的所有 a[pos] 保留,那么这个数量就是 cnt[a[pos]] ,而最后一个 a[pos] 出现的位置为 R_{a[pos]},所以也考虑也要算上 dp[R_{a[pos]}+1] 的答案。

所以这种情况下有
dp[i]=max(dp[i],cnt[a[i]]+dp[r[a[i]]+1])
② 如果当前位置 pos 不是这个颜色的左端点(即 L[a[pos]]\neq pos

那么我们如果要 强制保留 [pos,n] 的所有 a[pos] ,就必须将 [pos,n] 的所有不是 a[pos] 的数全部移动至后面(因为你会移动 pos 左边的 a[pos] 的颜色,所以即使右边非a[pos] 的颜色本身是连在一起的,也必须要移动。

举个例子

2 1 2 2 1 1 

如果有 pos=3a[pos]=2 ,如果我们要保留 [3,4] 的所有 2 ,那么因为 pos 之前还有等于 2 的数,那么pos 右边非 a[pos] 的都必须要移动,才能使 pos 前的 2 与这一片 2 连在一起。(说的罗嗦了)

所以这种情况下有
dp[i]=max(dp[i],cnt[a[i]])
而在一般情况下,由于从 i+1i 位置的跳跃,并不影响 i+1 之后的不需要移动书的最大数量,所以就有
dp[i]=dp[i+1]
总结一下便有
dp[i]=dp[i+1]
dp[i]=max(dp[i],cnt[a[i]]+dp[r[a[i]]+1])
dp[i]=max(dp[i],cnt[a[i]])

另外 这篇题解 将做题思路写了出来,感觉很符合开题后的思考逻辑,颇有帮助。

pic.png

代码

#include<bits/stdc++.h>
const int N = 5e5 + 10 ;
int n,dp[N],a[N],l[N],r[N],cnt[N];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        if(!l[a[i]]) l[a[i]]=i;
        r[a[i]]=i;
    }
    for(int i=n;i;--i){
        cnt[a[i]]++;
        dp[i]=dp[i+1];
        if(l[a[i]]!=i) dp[i]=std::max(dp[i],cnt[a[i]]);
        else dp[i]=std::max(dp[i],cnt[a[i]]+dp[r[a[i]]+1]);
    }
    printf("%d",n-dp[1]);
    return 0;
}
分类: DP

0 条评论

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注