E - Sorting Books

一排书架上有 $n$ 本书排成一排,每本书上有一个颜色 $a_i$,你可以每次将一本书移动到书架的最右端,如果书架上的书,颜色相同的书都排到了一块,我们就认为他是漂亮的,请问将这个书架通过上面的那一种操作排成漂亮的书架,最少需要几次操作?

Solution

其实是超级简单的一道题 ~

首先根据题意,先不考虑最优解,我们直接全部往右乱扔就一定能满足,但是不一定是最优解,解决最优解问题,很明显要么贪心,要么DP,要么贪心 + DP。

首先考虑贪心策略,我们一上来最直观的感受就是,如果有一种颜色,没有完全在一块,中间参杂着其他颜色的书,但是这种颜色的书的数量非常非常的多,很明显我们就可以贪心地把这种颜色中间的书移走,这些这种颜色的书就会自动合并到一块,肯定比把这种颜色的很多很多的书一个一个丢到最右边要来的快,这一点很容易想到。

所以我们来尝试找一下,有没有这种颜色的书,或者好几种,只要区间不重叠就好,数量比它中间其他颜色的书的数量还要多,也就是找到若干个区间,但是直接找区间有点困难,题目只需要我们输出最少操作次数即可,所以在有了这个完美的贪心策略以后,我们考虑DP来模拟这个过程。

我们设 $f[i]$ 表示 $i\cdots n$ 区间里不需要移动的书的最大数量,很显然答案就是 $n-f[1]$。除去不需要移动的,把剩下的按照颜色的分类丢到右边就行了。

我们想要找到的是区间里书数量最多的颜色,并且可以是很多种区间不重叠的颜色,要先找区间,所以我们先存一下每种颜色的出现的左右区间 $l_i$ 和 $r_i$ ,因为要找数量最多的那一种,所以我们再使用 $cnt$ 数组存一下每种颜色出现的次数。因为现在考虑的是逆序 DP,所以再存一下 $\text cnt\_post_i$ ,表示的是 $i\cdots n$ 之间每种颜色的书的数量。

考虑转移方程:

(1)$\tt f\ [i] = \max\{f\ [i], f[i + 1]\}$

(2)$\tt f[i] = \max\{f [i], {cnt\_post} [ a[ i]]\}$

我们取 $i\cdots n$ 里当前最优的一种颜色,也就是只选择一个区间的情况。为什么不能写成 $\tt f[i] = \max\{f [i], {cnt\_post} [ a[ i]]+f[r[a[i]]+1]\}$ 呢,也就是为什么我们不能一块加上当前颜色区间右边的最优解呢?这样看上去好像没什么毛病呀?

参见样例:

5
1 2 2 1 3
2

会发现如果在没有完全完整的区间的基础之上更新,就会导致几个区间重叠,得到实际上是错误的 “最优解”

(3)当 $\tt l[a[i]]=i$时,$\tt f[i]=max\{cnt[a[i]]+f[r[a[i]]+1]\}$

这里我们已经完全走完了颜色 $\tt a[i]$ 的整个区间,可以跟其他区间合并以找到最优解,也不会导致区间重叠。

这个转移方程实际上就是选择区间 $[l_{a_i},r_{a_i}]$ 里,颜色 $a_i$ 不移动,因为 $f[i]$ 存的是 $i\cdots n$ 里不需要移动的书的最大数量,所以要加上 $r_{a_i}$ 右边的 $f$ ,应该很好理解 ~

Code

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;
const int N = 5e5 + 7, mod = 1e9 + 7;
typedef long long ll;
typedef int itn;

itn a[N], l[N], r[N];
int cnt[N], cnt_post[N];
itn n, m;
int f[N];

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++ i) {
        scanf("%d", &a[i]);
        if(l[a[i]] == 0) l[a[i]] = i;
        r[a[i]] = i;
        cnt[a[i]] ++ ;
    }

    for(int i = n; i >= 1; -- i) {
        f[i] = f[i + 1];
        cnt_post[a[i]] ++ ;
        if(i == l[a[i]])
            f[i] = max(f[i], f[r[a[i]] + 1] + cnt[a[i]]);
        else f[i] = max(f[i], cnt_post[a[i]]);
    }
    printf("%d\n", n - f[1]);
    return 0;
}

当然,我们上面使用逆序来求,实际上正序逆序没有任何区别 ~


牛逼群友用线段树搞出来了...

wxyyyds

%%%

我还没看懂啥意思

#include <iostream>

namespace wxy{
const int N = 5e5 + 5,inf = 1e9 + 5;
#define int long long
int a[N],f[N],lst[N],fst[N],pre[N],cnt[N],n;
struct node{int l,r,add,max;}t[N << 2];
inline void pushup(int u){t[u].max = std::max(t[u << 1].max,t[u << 1 | 1].max);}
inline void pushdown(int u){
    if (t[u].add){
        t[u << 1].max += t[u].add; t[u << 1 | 1].max += t[u].add;
        t[u << 1].add = t[u << 1 | 1].add = t[u].add; t[u].add = 0; 
    }
}
inline void build(int u,int l,int r){
    t[u].l = l; t[u].r = r; t[u].add = 0;
    if (l == r){t[u].max = cnt[l]; return;}
    int mid = l + r >> 1;
    build(u << 1,l,mid);
    build(u << 1 | 1,mid + 1,r);
    pushup(u);
}
inline void cge(int u,int l,int r,int v){
    if (t[u].l == l && t[u].r == r){
        t[u].max += v; t[u].add += v;
        return;
    }
    int mid = t[u].l + t[u].r >> 1;
    pushdown(u);
    if (r <= mid) cge(u << 1,l,r,v);
    else if (l > mid) cge(u << 1 | 1,l,r,v);
    else {cge(u << 1,l,mid,v); cge(u << 1 | 1,mid + 1,r,v);}
    pushup(u);
}
inline int query(int u,int l,int r){
    if (t[u].l == l && t[u].r == r) return t[u].max;
    pushdown(u);
    int mid = t[u].l + t[u].r >> 1;
    if (r <= mid) return query(u << 1,l,r);
    else if (l > mid) return query(u << 1 | 1,l,r);
    else return std::max(query(u << 1,l,mid),query(u << 1 | 1,mid + 1,r));
}
inline void main(){
    std::cin >> n;
    for (int i = 1; i <= n; i++) std::cin >> a[i];
    for (int i = 1; i <= n; i++){
        pre[i] = lst[a[i]];
        lst[a[i]] = i;
        cnt[a[i]]++;
    }
    int pos = n;
    for (int i = n; i >= 1; i--){
        if (a[i] == a[n]) pos = i;
        else break;
    }
    int cr = cnt[a[n]] - (n - pos + 1);
    for (int i = 1; i <= n; i++)
        if (i != a[n]) cr += cnt[i];
    for (int i = 1; i <= n; i++)
        if (fst[a[i]] == 0) fst[a[i]] = i;
    int premax = 0;
    for (int i = 1; i <= n; i++){
        if (fst[a[i]] == i){
            f[i] = 1;
            f[i] = std::max(f[i],premax + 1);
        }else{
            f[i] = f[pre[i]] + 1;
        }
        if (lst[a[i]] == i) premax = std::max(premax,f[i]);
    }
    int ct = 0;
    int ans = n - f[n];
    for (int i = 1; i <= n; i++){
        if (a[i] == a[n]) continue;
        if (lst[a[i]] == i) ans = std::min(ans,cr - f[i]);
    }
    for (int i = 1; i <= n; i++)
        if (cnt[i] == 0) cnt[i] = -inf;
    build(1,1,n);  
    for (int i = 1; i <= n; i++){
        cge(1,a[i],a[i],-1);
        if (lst[a[i]] != i) continue;
        if (a[i]-1>=1)cge(1,1,a[i]-1,f[i]);
        if (a[i]+1<=n)cge(1,a[i]+1,n,f[i]);
        ans = std::min(ans,n - query(1,1,n));
        if (a[i]-1>=1)cge(1,1,a[i]-1,-f[i]);
        if (a[i]+1<=n)cge(1,a[i]+1,n,-f[i]);
    }
   std::cout << ans;
}
}signed main(){wxy::main(); return 0;}