CF868F题解

PenguinJ · 2025-08-19 18:50:07 · 题解

先考虑朴素的暴力，设 f_{k,i} 表示前 i 个数划分为 k 段的最小代价，有 f_{k,i}=\min_j\{f_{k-1,j-1}+w(j,i)\} ，其中， w(x,y) 表示 [x,y] 中相同元素的对数。

可以先在外层枚举 k ，考虑如何处理 f_i 的转移。记数组 g 为枚举上一个 k 时的 f 。假设有转移决策点 u 和 v,u<v ，假设 i 从 v 转移，则有g_v+w(v+1,i)<g_u+w(u+1,i) ，由于区间 [u+1,i] 中的数的种类不少于区间 [v+1,i] ，所以w(u+1，i+1) \geq w(v+1,i+1) ，即 g_v+w(v+1,i+1)<g_u+w(u+1,i+1) ，也就是说，对于大于 i 的点，都不会从 u 转移，即 f_i 具有决策单调性。

考虑整体二分。待转移区间 [l,r] ，和决策点区间 [fl,fr] ，对于 [l,r] 的中点 mid ，暴力的找出其对应的决策点 pos ，然后递归处理即可。

如何计算 w(x,y) ，可以使用类似莫队的东西去维护，均摊下来复杂度是 O(1) 的。

总的复杂度就是 O(kn\log n) 的。

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,k,a[100005],f[100005],g[100005],cnt[100005],ml,mr,w;
inline void add(ll x){if(x)w+=cnt[a[x]],cnt[a[x]]++;}
inline void del(ll x){if(x)cnt[a[x]]--,w-=cnt[a[x]];}
inline void move(ll l,ll r){
    while(mr<r)add(++mr);
    while(ml>l)add(--ml);
    while(mr>r)del(mr--);
    while(ml<l)del(ml++);
}
void solve(ll l,ll r,ll fl,ll fr){
    if(fl==fr){ 
        for(ll i=l;i<=r;i++){
            move(fl,i);
            f[i]=g[fl-1]+w;
        }
        return ;
    }
    ll mid=(l+r)>>1,pos,minn=1e16;
    for(ll i=fl;i<=min(fr,mid);i++){
        move(i,mid);
        ll v=g[i-1]+w;
        if(v<=minn)minn=v,pos=i;
    }
    f[mid]=minn;
    if(l==r)return ;
    solve(l,mid,fl,pos);
    solve(mid+1,r,pos,fr);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(ll i=1;i<=n;i++){
        cin>>a[i];
        g[i]=g[i-1]+cnt[a[i]];
        cnt[a[i]]++;
    }
    memset(cnt,0,sizeof(cnt));
    w=0;
    for(ll i=2;i<=k;i++){
        solve(1,n,1,n);
        for(ll j=1;j<=n;j++)g[j]=f[j];
    }
    cout<<g[n];
    return 0;
}