题目链接 BZOJ 3675
首先最后的答案和分割的顺序是无关的，
那么就可以考虑DP了。
设$f[i][j]$为做了$i$次分割，考虑前$j$个数之后的最优答案。
那么$f[i][j] = max(f[i - 1][p] + (s[i] - s[p]) * s[p])$
时间复杂度为$O(kn^{2})$，TLE。
假设$j>k$且在$j$点的决策优于在$k$点的决策，
把不等式移项，我们发现这个DP可以斜率优化。
这样时间复杂度就降到了$O(kn)$。
空间的话滚动数组就可以了。
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i) typedef long long LL; const int N = 1e5 + 10; LL f[2][N], s[N], a[N];
int q[N];
int n, l, r, k;
int tmp = 0; inline LL Y(int k){ return s[k] * s[k] - f[tmp ^ 1][k]; }
inline LL X(int k){ return s[k]; }
inline LL getup(int x1, int x2){ return Y(x1) - Y(x2);}
inline LL getdown(int x1, int x2){ return X(x1) - X(x2);} void solve(){
tmp ^= 1;
l = 0, r = 0, q[r++] = 0;
rep(i, 1, n){
while (l + 1 < r && getup(q[l + 1], q[l]) <= getdown(q[l + 1], q[l]) * s[i]) ++l;
f[tmp][i] = f[tmp ^ 1][q[l]] + (s[i] - s[q[l]]) * s[q[l]];
while (l + 1 < r && getup(i, q[r - 1]) * getdown(q[r - 1], q[r - 2]) <=
getup(q[r - 1], q[r - 2]) * getdown(i, q[r - 1])) --r;
q[r++] = i;
}
} int main(){ scanf("%d%d", &n, &k);
rep(i, 1, n) scanf("%lld", a + i);
s[0] = 0;
rep(i, 1, n) s[i] = s[i - 1] + a[i];
tmp = 0;
rep(i, 1, k) solve();
printf("%lld\n", f[tmp][n]);
return 0; }