传送门

听亲妈聊耽美和魔道祖师是种什么体验

令$S_i$为分成$k+1$段后第$i$段的和。

考虑任意的第$i$段和第$j$段（$i\neq j$）之间的贡献，一定会存在某次分割使它们分开，产生$S_iS_j$的贡献，之后两者再无关联。

所以答案为$\sum\limits_{i=1}^{k+1}\sum\limits_{j=i+1}^{k+1}S_iS_j$，与分割顺序无关。

把这个式子变一变：$\dfrac{\left(\sum\limits_{i=1}^{k+1}S_i\right)^2-\sum\limits_{i=1}^{k+1}S_i^2}{2}$

$\left(\sum\limits_{i=1}^{k+1}S_i\right)^2$就是整个序列的和的平方，我们的任务就成了最小化$\sum\limits_{i=1}^{k+1}S_i^2$。

设$s_i$为数列前缀和，$f(i,j)$为前$i$个数分成$j$段的最小代价。

显然，$f(i,k)=\min\limits_{j<i}\{f(j,k-1)+(s_i-s_j)^2\}$

变个形：$f(j,k-1)+s_j^2=f(i,k)+2s_is_j-s_i^2$

然后就能斜率优化了。有一个坑点是序列可能有$0$，所以斜率可能不存在。

复杂度$O(nk)$。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define maxn 100005
#define inf 0x3f3f3f3f

using namespace std;

inline int read(){
    int x=0,y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
long long f[maxn][2],y[maxn];
int x[maxn],g[maxn][205],p[maxn],s[maxn],head,tail;
inline void clear(){head=1,tail=0;}
inline void push(int xx,long long yy,int pos){
    while(head<tail&&xx!=x[tail]&&(x[tail]==x[tail-1]||(double)(y[tail]-y[tail-1])/(x[tail]-x[tail-1])>(double)(yy-y[tail])/(xx-x[tail])))--tail;
    x[++tail]=xx,y[tail]=yy,p[tail]=pos;
}
inline int front(int k){
    while(head<tail&&(double)(y[head+1]-y[head])<=1ll*k*(x[head+1]-x[head]))++head;
    return p[head];
}
inline long long sqr(int x){return 1ll*x*x;}
int main(){
    int n=read(),k=read()+1;
    for(register int i=1;i<=n;++i)f[i][1]=sqr(s[i]=s[i-1]+read());
    for(register int j=2;j<=k;++j){
        clear(),push(s[j-1],f[j-1][j&1^1]+sqr(s[j-1]),j-1);
        for(register int i=j;i<=n;++i){
            int J=g[i][j]=front(s[i]<<1);
            f[i][j&1]=f[J][j&1^1]+sqr(s[i]-s[J]);
            push(s[i],f[i][j&1^1]+sqr(s[i]),i);
        }
    }
    printf("%lld\n",1ll*s[n]*s[n]-f[n][k&1]>>1);
    for(register int j=k,i=n;j>1;--j)printf("%d ",i=g[i][j]);
    pn;
}