首先易证分割的顺序对答案没有影响（\((a + b) c + ab = a (b + c) + bc\)）。
然后设 \(F_{i,k}\) 表示前 \(i\) 个数分割了 \(k\) 次的得分。
有转移 \(F_{i,k} = \max\limits_{0 \le j < i} (F_{j,k - 1} + sum_j (sum_i - sum_j))\)，其中 \(sum_i = \sum\limits_{j = 1}^i a_i\)。
把第二维滚动，设 \(f_i = F_{i,k},g_i = F_{i,k - 1}\)，式子变为 \(f_i = \max\limits_{0 \le j < i} (g_j + sum_j (sum_i - sum_j))\)。
对于 \(0 \le k < j < i\)，设 \(j\) 优于 \(k\)，有 \[\begin{align*} g_j + sum_j (sum_i - sum_j) & \ge g_k + sum_k (sum_i - sum_k) \\ g_j + sum_j sum_i - sum_j^2 & \ge g_k + sum_k sum_i - sum_k^2 \\ (g_j - sum_j^2) - (g_k - sum_k^2) & \ge (sum_k - sum_j) sum_i \\ \dfrac{(g_j - sum_j^2) - (g_k - sum_k^2)}{sum_k - sum_j} & \le sum_i \end{align*}\]
注意特判 \(sum_j = sum_k\) 的情况，这时斜率为 \(-\infty\)。
维护一只下凸包即可。
输出方案的话，中途记录一下选择的决策。
然鹅 BZOJ 不需要输出方案……
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
using namespace std;
const int N = 1e5;
const int K = 200;
int n,k;
int a[N + 5],pre[N + 5][K + 5];
int q[N + 5],head,tail;
long long sum[N + 5],f[N + 5],g[N + 5];
inline double slope(int x,int y)
{
if(sum[x] == sum[y])
return -0x3f3f3f3f3f3f3f3f;
return (double)(g[x] - sum[x] * sum[x] - g[y] + sum[y] * sum[y]) / (sum[y] - sum[x]);
}
int main()
{
scanf("%d%d",&n,&k);
for(register int i = 1;i <= n;++i)
scanf("%d",a + i),sum[i] = sum[i - 1] + a[i];
for(register int i = 1;i <= k;++i)
{
q[head = tail = 1] = 0;
for(register int j = 1;j <= n;++j)
{
for(;head < tail && slope(q[head],q[head + 1]) <= sum[j];++head);
f[j] = g[q[head]] + sum[q[head]] * (sum[j] - sum[q[head]]),pre[j][i] = q[head];
for(;head < tail && slope(q[tail - 1],q[tail]) >= slope(q[tail],j);--tail);
q[++tail] = j;
}
for(register int j = 1;j <= n;++j)
g[j] = f[j];
}
printf("%lld\n",f[n]);
/*
for(register int i = n,j = k;j;--j)
printf("%d ",i = pre[i][j]);
此处为输出方案，由于 BZOJ 没有 SPJ 所以省去该步骤。
*/
}