解析
首先我们得明确：分割的顺序是无所谓的
不然我们很难列出转移方程
那为什么呢？
假若当前我们把某段序列分成三段，依次记为 \(x,y,z\)，每段和记为 \(s_x , s_y , s_z\)
那么如果我们先分出 \(x,y\) ，那么 \(ans = s_x \times (s_y+s_z) + s_y \times s_z\)
另一种 \(ans = (s_x + s_y) \times s_z + s_x \times s_y\)
可以发现两种是一样的
好了，那么我们就可以有 \(f_{i,l} = f_{j,l-1} + s_j \times (s_i-s_j)\)
然后套路斜率优化
\(j>k\) 最后有
\[\frac{(f_{j,l-1} - s_j^2)-(f_{k,l-1} - s_k^2)}{(-s_j)-(-s_k)} < s_i
\]
维护下凸壳，单调队列即可
\(Code\)
#include<cstdio>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5;
LL f[N][2] , s[N];
int n , k , pre[N][205] , q[N] , l , r;
double slope(int t , int u , int v)
{
if (s[u] == s[v]) return 1.0 / 0.0;
return 1.0 * (f[u][t & 1] - s[u] * s[u] - (f[v][t & 1] - s[v] * s[v])) / (s[v] - s[u]);
}
int main()
{
scanf("%d%d" , &n , &k);
for(register int i = 1; i <= n; i++) scanf("%d" , s + i) , s[i] += s[i - 1];
for(register int t = 1; t <= k; t++)
{
l = r = 1;
for(register int i = 1; i <= n; i++)
{
while (l < r && slope(t - 1 , q[l] , q[l + 1]) < s[i]) l++;
f[i][t & 1] = f[q[l]][t & 1 ^ 1] + s[q[l]] * (s[i] - s[q[l]]);
pre[i][t] = q[l];
while (l <= r && slope(t - 1 , q[r] , q[r - 1]) > slope(t - 1 , q[r] , i)) r--;
q[++r] = i;
}
}
printf("%lld\n" , f[n][k & 1]);
int x = n;
while (pre[x][k] != 0) printf("%d " , pre[x][k]) , x = pre[x][k--];
}