CF868F Yet Another Minimization Problem

LXI.CF868F Yet Another Minimization Problem

这种题一般来说只有决策单调性一种优化方法。不过,决策单调性可以有很多种应用,例如单调队列或是斜率优化。这题可以选择比较少见的分治优化。

明显,可以设\(f[i][j]\)表示前\(i\)个位置分成\(j\)段的最大收益。显然,暴力是\(O(n^2k)\)的。

如果我们按照\(j\)一遍一遍地跑的话,是可以考虑在\(i\)上面进行优化的、

考虑设\(f[i]\)表示\(f[i][j-1]\),\(g[i]\)表示\(f[i][j]\),

然后设\(w[l,r]\)表示区间\([l,r]\)的费用,

则我们是否可以证明它具有决策单调性?

即:

对于\(\forall i_1<i_2\),设它们分别从\(j_1\),\(j_2\)转移来最优,则必有\(j_1\leq j_2\)。

则必有

\(g_{j_1}+w[j_1+1,i_1]\leq g_{j_2}+w[j_2+1,i_1],g_{j_2}+w[j_2+1,i_2]\leq g_{j_1}+w[j_1+1,i_2]\)

我们可以考虑反证法。假设有\(j_1>j_2\),

则对于上面的两个不等式里,如果两个都取到了\(=\),则交换\(j_1,j_2\)没有影响。

否则,我们不妨设在第一个式子里取到了\(<\),

\(g_{j_1}+w[j_1+1,i_1]<g_{j_2}+w[j_2+1,i_1],g_{j_2}+w[j_2+1,i_2]\leq g_{j_1}+w[j_1+1,i_2]\)

移项得

\(w[j_1+1,i_1]-w[j_2+1,i_1]<g_{j_2}-g_{j_1},g_{j_2}-g_{j_1}\leq w[j_1+1,i_2]-w[j_2+1,i_2]\)

两边合并\(g_2-g_1\),得

\(w[j_1+1,i_1]-w[j_2+1,i_1]<w[j_1+1,i_2]-w[j_2+1,i_2]\)

这两项全部只有后面的\(i_1\)和\(i_2\)不同。但\(i_1<i_2\),因此这是不可能成立的,往区间后面加数后答案必不会减少。

然后就可以分治了。每一轮我们存储对于当前区间\([l,r]\)可行的决策点\([L,R]\),对于\([l,r]\)的中点\(mid\),我们找到最优转移位置\(mp\),然后继续分治\(([l,mid-1],[L,mp])\)与\(([mid+1,r],[mp,R])\)。

关于如何计算\(w[l,r]\)吗……类似的莫队一下,因为单次分治中左右端点总移动距离是\(n\log n\)的(每一层里面左右端点总次数是\(O(n)\)的,然后一共\(\log n\)层)。

总复杂度\(O(nk\log n)\)。

代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,num[101000],cnt[101000],res,f[100100],g[100100];
int u,v;
void Push(int x){
	res+=cnt[num[x]],cnt[num[x]]++;
}
void Pop(int x){
	cnt[num[x]]--,res-=cnt[num[x]];
}
int Calc(int l,int r){
	while(u>l)Push(--u);
	while(v<r)Push(++v);
	while(u<l)Pop(u++);
	while(v>r)Pop(v--);
	return res;
}
void solve(int l,int r,int L,int R){
	if(l>r||L>R)return;
	int mp=-1,mn=0x3f3f3f3f3f3f3f3f,mid=(l+r)>>1;
	for(int i=L;i<=R;i++){
		int tmp=Calc(i+1,mid);
		if(f[i]+tmp<mn)mp=i,mn=f[i]+tmp;
	}
	g[mid]=mn;
	solve(l,mid-1,L,mp),solve(mid+1,r,mp,R);
}
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)scanf("%lld",&num[i]);
	u=v=1,cnt[num[1]]++;
	for(int i=1;i<=n;i++)f[i]=Calc(1,i);
	while(--m)solve(1,n,0,n-1),memcpy(f,g,sizeof(g));
	printf("%lld\n",f[n]);
	return 0;
}

上一篇:CF868F Yet Another Minimization Problem(DP+整体二分)


下一篇:python – 在Sympy中,什么相当于Mathematica的符号最小化函数?