CF868F Yet Another Minimization Problem 决策单调性

题意：

显然的 DP 式子 (f_{i,j}=min f_{k,j-1}+w(k,i))

滚掉第二维可以化简为 (g_i=min f_k+w(k,i))

这个式子符合决策单调性，证明：

$forall a<b<c<d w(a,c)+w(b,d)le w(a,d)+w(b,c)且w(b,c)le w(a,d) $

由于 ((b,c)in(a,d)) 所以 (w(b,c)le w(a,d)) 所以第二个式子显然成立

那么我们开始推第一个式子

(w(b,d)-w(b,c)le w(a,d)-w(a,c))

我们记 (val(x,y,z,w)) 表示 ([z,w]) 中与 ([x,y]) 中相同的元素对数

那么原式等价于

(val(b,c,c,d)le val(a,c,c,d))

由于 ([b,c]in[a,c]) 所以 ([a,c]) 中元素对数不少于 ([b,c]) 中元素对数所以上式显然成立

(QED.)

---

好，既然知道了 DP 可以决策单调性优化，那么我们可以考虑 二分栈 或者 分治

由于二分栈有一个弊端就是必须能快速计算 (w(i,j)) 不然二分时统计答案复杂度过大就会白给，但不巧这个题不能快速计算 (w(i,j)) 所以我们只能采取分治写法

每次划分决策区间和二分区间，找最优决策点的时候只用暴力挪指针，开个桶更新一下相同元素对数，由于每个元素被挪次数不超过 (log) 次

所以总复杂度是 (O(nlog ))

代码：

#include<bits/stdc++.h>

using namespace std;

namespace zzc
{
	const int maxn = 1e5+5;
	long long f[25][maxn];
	int a[maxn],num[maxn];
	int n,m,cur,L,R;
	long long ans; 
	
	void calc(int l,int r)
	{
		while(l<L) L--,ans+=num[a[L]],num[a[L]]++;
		while(R<r) R++,ans+=num[a[R]],num[a[R]]++;
		while(l>L) num[a[L]]--,ans-=num[a[L]],L++;
		while(R>r) num[a[R]]--,ans-=num[a[R]],R--;
	}
	
	void solve(int l,int r,int ll,int rr)
	{
		if(l>r) return ;
		int mid=(l+r)>>1,p;
		for(int i=ll;i<=min(mid,rr);i++)
		{
			calc(i+1,mid);
			if(f[cur-1][i]+ans<f[cur][mid])
			{
				f[cur][mid]=f[cur-1][i]+ans;
				p=i;
			}
		}
		solve(l,mid-1,ll,p);
		solve(mid+1,r,p,rr);
	}
	
	void work()
	{
		memset(f,0x7f,sizeof(f));
		scanf("%d%d",&n,&m);L=1;
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		for(int i=1;i<=n;i++) calc(1,i),f[1][i]=ans;
		for(int i=2;i<=m;i++) cur=i,solve(1,n,1,n);
		printf("%lld
",f[m][n]);
	}

}

int main()
{
	zzc::work();
	return 0;
}