Description：

把一个长为 $n$ 的块切成 $k+1$ 块，每次获得两个新产生的块的元素和的乘积的分数，最大化最后的总得分。

$1\le n \le 100000$

Solution：

可以发现得分只与切的位置有关而与切的顺序无关，所以状态转移方程为 $f[i][k]=\max(f[j][k-1]+(s[i]-s[j])\times s[j])$ ，可以用斜率优化进行优化，式子变形后为 $f[j][k-1]-s[j]\times s[j]=-s[i]\times s[j]+f[i][k]$ ， $y=f[j][k-1]-s[j]\times s[j],x=s[j],k=-s[i],b=f[i][k]$

横坐标单调递增， $k$ 单调递减，维护一个上凸壳就行了。

注意斜率优化一定要判断相等的情况，不然会卡在一个相等的位置不往后动。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,k;

#define MAXN 100010

#define MAXK 201

typedef long long ll;

ll a[MAXN],sum[MAXN];

ll f[2][MAXN];

ll y[MAXN];

int q[MAXN],head,tail;

double slope(int cur,int a,int b)

{

	return (double)((f[cur][a] - sum[a] * sum[a]) - (f[cur][b] - sum[b] * sum[b])) / (double)(sum[a] - sum[b]);

}

int g[MAXK][MAXN];

int s[MAXN],top = 0;

int main()

{

	scanf("%d%d",&n,&k);

	for(int i = 1;i <= n;++i)scanf("%lld",&a[i]);

	for(int i = 1;i <= n;++i)sum[i] = sum[i - 1] + a[i];

	memset(f,0xc0,sizeof(f));

	f[0][0] = 0;y[0] = 0;

	int cur = 0;

	for(int i = 1;i <= k + 1;++i)

	{

		head = 1;tail = 0;

		cur = cur ^ 1;

		memset(f[cur],0xc0,sizeof(f[cur]));

		q[++tail] = 0;

		for(int j = 1;j <= n;++j)

		{

			while(head < tail && -(double)sum[j] * (double)(sum[q[head + 1]] - sum[q[head]]) <= (double)(y[q[head + 1]] - y[q[head]]))++head;

			f[cur][j] = f[cur ^ 1][q[head]] + (sum[j] - sum[q[head]]) * sum[q[head]];

			g[i][j] = q[head];//cout << q[head] << endl;

			while(head < tail && (double)(y[j] - y[q[tail]]) * (double)(sum[q[tail]] - sum[q[tail - 1]]) >= (double)(y[q[tail]] - y[q[tail - 1]]) * (double)(sum[j] - sum[q[tail]]))--tail;

			q[++tail] = j;y[j] = f[cur ^ 1][j] - sum[j] * sum[j];//cout << i << " " << j << " " << f[cur][j] << endl;

		}

	}

	int pos = n;

	int w = k + 1;

	while(g[w][pos] != 0)

	{

		s[++top] = g[w][pos];

		pos = g[w][pos];

		--w;

	}

	cout << f[cur][n] << endl;

	for(int i = top;i >= 1;--i)printf("%d ",s[i]);

	puts("");

	return 0;

}