专栏文章

CF868F题解

PPenguinJ
CF868F题解参与者 1已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mio8rxxi
此快照首次捕获于
2025/12/02 15:13
3 个月前
此快照最后确认于
2025/12/02 15:13
3 个月前
查看原文
先考虑朴素的暴力，设 fk,if_{k,i} 表示前 ii 个数划分为 kk 段的最小代价，有 fk,i=min⁡j{fk−1,j−1+w(j,i)}f_{k,i}=\min_j\{f_{k-1,j-1}+w(j,i)\} ，其中， w(x,y)w(x,y) 表示 [x,y][x,y] 中相同元素的对数。
可以先在外层枚举 kk ，考虑如何处理 fif_i 的转移。记数组 gg 为枚举上一个 kk 时的 ff 。假设有转移决策点 uu 和 v,u<vv,u<v ，假设 ii 从 vv 转移，则有gv+w(v+1,i)<gu+w(u+1,i)g_v+w(v+1,i)<g_u+w(u+1,i) ，由于区间 [u+1,i][u+1,i] 中的数的种类不少于区间 [v+1,i][v+1,i] ，所以w(u+1，i+1)≥w(v+1,i+1)w(u+1，i+1) \geq w(v+1,i+1) ，即 gv+w(v+1,i+1)<gu+w(u+1,i+1)g_v+w(v+1,i+1)<g_u+w(u+1,i+1) ，也就是说，对于大于 ii 的点，都不会从 uu 转移，即 fif_i 具有决策单调性。
考虑整体二分。待转移区间 [l,r][l,r] ，和决策点区间 [fl,fr][fl,fr] ，对于 [l,r][l,r] 的中点 midmid ，暴力的找出其对应的决策点 pospos ，然后递归处理即可。
如何计算 w(x,y)w(x,y) ，可以使用类似莫队的东西去维护，均摊下来复杂度是 O(1)O(1) 的。
总的复杂度就是 O(knlog⁡n)O(kn\log n) 的。
代码：
CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...