首先容易证明，得分和切的顺序没有关系
所以直接默认先切左边再切右边就好了
然后显然可以 $dp$
一开始想的是设 $f[i][j]$ 表示切了 $i$ 次，此次把 $j$ 和 $j+1$ 分开，得到的最大价值
那么显然枚举上一次切的位置 $k$ ，那么 $f[i][j]=f[i-1][k]+(sum[j]-sum[k])(sum[n]-sum[j])$
这个东西是可以斜率优化+滚动数组，但是很不好写，一堆边界问题要想，代码就不放了（亲自尝试发现甚至会爆$long long$）
另一个好的思路：设 $f[i][j]$ 表示已经切了 $i$ 次，只考虑前面 $j$ 块的最大价值
同样枚举 $k$，$f[i][j]=f[i-1][k]+(sum[i]-sum[j])*sum[j]$
这样式子就好化了：$f[i][j]=f[i-1][k]+sum[i]sum[j]-sum[j]^2$
：$-sum[i]sum[j]+f[i][j]=f[i-1][k]-sum[j]^2$
那么 $k=-sum[i],x=sum[j],b=f[i][j],y=f[i-1][k]-sum[j]^2$
发现 $k,x$ 都单调，所以直接斜率优化就好了，同样要滚动数组
注意原序列可能有 $0$，那么 $x$ 就不是单调上升而是单调不增，求斜率时要注意特判 $x$ 相同的情况！
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<vector> using namespace std; typedef long long ll; typedef long double ldb; inline int read() { register int x=0,f=1; static char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=1e5+7; int n,m; ll sum[N],f[2][N]; inline ll X(int x) { return sum[x]; } inline ll Y(int x) { return f[1][x]-sum[x]*sum[x]; } inline ldb slope(int i,int j) { if(X(i)==X(j)) return Y(i)>Y(j) ? -1e18 : 1e18; return (ldb)(Y(i)-Y(j))/(X(i)-X(j)); } int Q[N],l,r; int main() { n=read(); m=read(); register int i,j; for(i=1;i<=n;i++) sum[i]=sum[i-1]+read(); for(j=1;j<=m;j++) { l=r=1; for(i=1;i<=n;i++) { while(l<r && -sum[i]<=slope(Q[l],Q[l+1]) ) l++; int &k=Q[l]; f[0][i]=f[1][k]+(sum[i]-sum[k])*sum[k]; while(l<r && slope(Q[r-1],Q[r]) <= slope(Q[r],i) ) r--; Q[++r]=i; } swap(f[0],f[1]); } printf("%lld ",f[1][n]); return 0; }