lp3648 APIO2014 序列分割

首先证明序列分割的次序和最后的答案毫无关系。
这可以用乘法的基本性质证明。例如分成三段，我们有：
$$a(b+c)+bc=b(a+c)+ac$$

我们可以进行DP。
我们记\(f_{i,k}\)表示当前访问到第\(i\)个点，使用了\(k\)次切割的答案。
那么根据题目中贡献的定义，我们有：
$$f_{i,k}=max_{j=k}^{i-1}{f_{j,k-1}+sm_{j}(sm_{i}-sm_{j})}$$ 令\(k\le j_1(sm_i-sm_{j_1})\le f_{j_2,k-1}+sm_{j_2}(sm_i-sm_{j_2})\)$ 展开，移项，合并。 $$f_{j_1,k-1}+sm_{j_1}sm_i-sm_{j_1}^2\le f_{j_2,k-1}+sm_{j_2}sm_i-sm_{j_2}^2$$ $$f_{j_1,k-1}-f_{j_2,k-1}+sm_{j_2}^2-sm_{j_1}^2\le sm_{j_2}sm_i-sm_{j_1}*sm_i$$
$$\frac{f_{j_1,k-1}-f_{j_2,k-1}+sm_{j_2}^2-sm_{j_1}^2}{sm_{j_2}-sm_{j_1}}\le sm_i$$
这个式子显然是可以斜率优化的。
这样做的时空复杂度是\(O(nk)\)的。
考虑到这一题的空间限制比较紧张，我们可以用滚动数组把\(k\)这一维压掉。

#include<iostream>
#include<cstdio>

int q[100005];
long long f[100005][2],sm[100005];
int ans[100005][205],n,K;
inline double slope(int j1,int j2,int k){
	return (sm[j1]^sm[j2])?(double)(f[j1][(k&1)^1]-f[j2][(k&1)^1]+sm[j2]*sm[j2]-sm[j1]*sm[j1])/(double)(sm[j2]-sm[j1]):-1E18;
} 
void init(){
	scanf("%d%d",&n,&K);
	for(int i=1;i<=n;++i){
		scanf("%lld",&sm[i]);
		sm[i]+=sm[i-1];
	}
	for(int i=1;i<=K;++i){
		int l,r;
		l=r=1;
		for(int j=1;j<=n;++j){
			while(l<r&&slope(q[l],q[l+1],i)<=sm[j]){
				++l;
			}
			f[j][i&1]=f[q[l]][(i&1)^1]+sm[q[l]]*(sm[j]-sm[q[l]]);
			ans[j][i]=q[l];
			while(l<r&&slope(q[r-1],q[r],i)>slope(q[r],j,i)){
				--r;
			}
			q[++r]=j;
		}
	}
	int nw=n;
	printf("%lld\n",f[n][K&1]);
	for(int i=K;i>=1;--i){
		nw=ans[nw][i];
		printf("%d ",nw);
	}
}

int main(){
	init();
	return 0;
}