[CF868F]Yet Another Minimization Problem

做题时间：2022.10.15

\(【题目描述】\)

给定一个长度为 \(n(2\leq n\leq 10^5)\) 的序列，把他分成 \(k(2\leq k\leq \min(n,20))\) 个子段，每个子段的花费是其中相同元素的对数，求所有子段的花费之和的最小值。

\(【输入格式】\)

第一行两个整数 \(n,k\)

第二行 \(n\) 个整数表示序列

\(【输出格式】\)

一行一个整数表示答案

\(【考点】\)

决策单调性优化dp、莫队

\(【做法】\)

设 \(f_{i,j}\) 表示将前 \(i\) 个数分割成 \(j\) 个子段的花费，有：

然后套路地使用分治去做。比较麻烦的是计算 \(val(l,r)\)，可以使用类似于莫队的思想，直接全局维护当前的求解区间 \([L,R]\)，然后每次计算的时候暴力移动左右端点即可。这相当于每层递归移动完父亲后移动儿子，因此单层的复杂度为 \(O(n)\)，总时间复杂度为 \(O(n\log n)\)

\(【代码】\)

#include<cstdio>
#include<iomanip>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=1e5+50,K=22;
int a[N],n,k;
ll f[N][K],ans;
int buc[N],L=1,R;
void add(int x){ans+=(ll)buc[x],buc[x]++;}//添加一个点
void del(int x){buc[x]--,ans-=(ll)buc[x];}//删除一个点

ll calc(int l,int r)//暴力移动并计算val[l,r]
{
	while(L>l) L--,add(a[L]);
	while(L<l) del(a[L]),L++;
	while(R<r) R++,add(a[R]);
	while(R>r) del(a[R]),R--;
	return ans;
}
void dp(int l,int r,int jl,int jr,int cur)
{
	if(l>r) return ;
	int mid=(l+r)>>1;
	int num=jl;
	for(int k=jl;k<=min(jr,mid);k++){
		ll t=f[k][cur-1]+calc(k+1,mid);
		if(t<f[mid][cur]) f[mid][cur]=t,num=k;
	}
	dp(l,mid-1,jl,num,cur);
	dp(mid+1,r,num,jr,cur);
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	memset(f,0x3f,sizeof f);
	f[0][0]=0;
	for(int i=1;i<=k;i++) dp(1,n,0,n-1,i);
	printf("%lld\n",f[n][k]);
	return 0;
}

原文地址：http://www.cnblogs.com/Unlimited-Chan/p/16794561.html