题解：P11311 漫长的小纸带

_Kenma_ · 2024-11-25 16:12:23 · 题解

P11311 解题报告

前言

怎么蓝了，那就写篇题解吧。

思路分析

套路地，设 f_i 表示到第 i 位的最小答案，易得转移：

其中 cal(l,r) 表示区间 [l,r] 的不同颜色种类数。

然后你大胆猜测有决策单调性，大力二分队列维护就做完了。

注意到答案上界为 n，也就是把序列断成 n 段，每段代价为 1。

因此，我们的合法转移区间 [j+1,i]，其中的颜色种类数必然 \le \sqrt{n}。

使用刷表法转移。考虑用一个链表记录当前每种颜色下一次出现的位置，用 set 维护这些位置。每次转移时，只需要转移 set 中当前颜色的 \sqrt{n} 个后继就行了。

不难发现复杂度是 O(n\sqrt{n}\log n) 的，感谢良心出题人没有卡 set 的巨大常数。

代码实现

#include<bits/stdc++.h>
using namespace std;
int n,a[200005],b[200005],pre[200005],suf[200005],f[200005],vis[200005];
set<int> s;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=a[i];
    }
    sort(b+1,b+1+n);
    int cnt=unique(b+1,b+1+n)-b-1;
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(b+1,b+1+n,a[i])-b;
    }
    for(int i=1;i<=n;i++){
        suf[pre[a[i]]]=i;
        pre[a[i]]=i;
    }
    s.insert(n+1);
    for(int i=1;i<=n;i++){
        if(!vis[a[i]]) s.insert(i); 
        vis[a[i]]=1;
    }
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for(int i=1;i<=n;i++){
        set<int>::iterator it=s.begin();
        it=next(it);
        for(int j=1;j*j<=n && it!=s.end();j++,it=next(it)){
            f[(*it)-1]=min(f[(*it)-1],f[i-1]+j*j);
        }
        s.erase(i);
        if(suf[i]){
            s.insert(suf[i]);
        }
    }
    cout<<f[n];
    return 0;
}