首先证明序列分割的次序和最后的答案毫无关系。
这可以用乘法的基本性质证明。例如分成三段，我们有：
$$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;
}