【CF868F】Yet Another Minimization Problem（分治决策单调性）

点此看题面

• 要求把一个长度为(n)的序列划分为(k)部分，定义一个区间的费用是其中相同元素对数，求所有段费用和的最小值。
• (nle10^5,kle20)

决策单调性优化(DP)

容易想到设(f_{i,j})表示把前(j)个数划分成(i)段的最小费用和。

显然，在(i)相同的时候，转移点具有单调性，因此可以决策单调性优化(DP)。

但是我们发现这都只是前置工作，此题最大的问题在于一个区间的费用定义为相同元素对数，是不好算的。

分治决策单调性

因此我们考虑分治决策单调性，这样的一大好处就是我们会一步一步枚举决策点，而像二分栈决策单调性每次都要跨一大段区间询问复杂度直接炸裂。

然后再仔细分析复杂度，发现左端点的移动是(O(决策区间))，右端点的移动是(O(分治区间))的，所以说：

实际上，我们只要采用类莫队形式，维护好每种颜色的出现次数，每次暴力移动左右端点维护答案即可。

于是就结束了。

代码：(O(knlogn))

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 100000
#define K 20
#define LL long long
using namespace std;
int n,k,a[N+5];LL f[K+1][N+5];
namespace FastIO
{
	#define FS 100000
	#define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
	char oc,FI[FS],*FA=FI,*FB=FI;
	Tp I void read(Ty& x) {x=0;W(!isdigit(oc=tc()));W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));}
	Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
}using namespace FastIO;
int L=1,R=0,c[N+5];LL t=0;I LL Calc(CI l,CI r)//询问[l,r]中相同元素对数
{
	W(R<r) t+=c[a[++R]]++;W(L>l) t+=c[a[--L]]++;W(R>r) t-=--c[a[R--]];W(L<l) t-=--c[a[L++]];return t;//暴力移动
}
I void DP(CI id,CI l,CI r,CI L,CI R)//分治决策单调性优化DP
{
	if(l>r) return;RI i,mid=l+r>>1,p=L;LL v=f[id-1][p]+Calc(p+1,mid);
	for(i=L+1;i<mid&&i<=R;++i) f[id-1][i]+Calc(i+1,mid)<v&&(v=f[id-1][p=i]+Calc(i+1,mid));f[id][mid]=v;//找到最优决策点
	DP(id,l,mid-1,L,p),DP(id,mid+1,r,p,R);//递归
}
int main()
{
	RI i,j;for(read(n,k),i=1;i<=n;++i) read(a[i]);
	for(i=0;i<=k;++i) for(j=0;j<=n;++j) f[i][j]=1e18;f[0][0]=0;//初始化
	for(i=1;i<=k;++i) DP(i,i,n,0,n-1);return printf("%lld
",f[k][n]),0;//枚举划分的段数转移，具有单调性
}