卡精度,你知道什么叫前人的经验的重要性吗?

首先我们考虑只砍第一刀,所以可以写出转移方程

$f_i=min_{j<i} {g_j + sum_j*(sum_i-sum_j)}$

然后我们能有:

$f_i=min_{j<i} {g_j -sum_j*sum_j + sum_j*sum_i}$

显然可以斜率优化

$y=g_j -sum_j*sum_j,x=sum_j,k_i=sum_i$最小化截距,所以维护的是上凸壳

然后你会发现这个y是小于0的,也就是说我们对于$x<y$

$gety(x)-gety(y)$大于0,但是$sum_x-sum_y$小于0

那么我们可以把$sum_k$*-1来去截取,也可以把斜率$*-1$来适配

但是正确性就没法用凸包想象了

另外一种思路是直接像推决策单调性一样找出更优的条件,好像也很适配,可以试试

细节

本题核心开始:

1. 卡精度,也就是说我们如果强制转换多了就人没了

你可能会说叉积判

2. $a_i$是非负整数,我们可以存在x相同的两个点

叉积判没了

code:

#include<bits/stdc++.h>
#define ll long long
#define db double
using namespace std;
const int MAXN = 1e5 + 7;
int n, m, k;
int a[MAXN], bck[205][MAXN];
ll f[MAXN], sum[MAXN], g[MAXN];

inline ll gety(int x) {
	return 1ll * g[x] - sum[x] * sum[x];
}

inline ll getk(int x) {
	return sum[x];
}

inline ll getx(int x) {
	return sum[x];
}

int hd, tl, que[MAXN];

inline db getslope(int i, int j) {
	if(getx(j) == getx(i))return -1e19;
	return (gety(i) - gety(j)) / ((db)getx(j) - getx(i));
}

inline ll calc(int j, int i) {
	return gety(j) + sum[j] * sum[i];
}

inline void solve() {
	hd = 1;
	tl = 0;
	que[1] = 0;
	for(int i = 1; i <= n; ++i) {
		//		printf("%d %d %lf %lld\n",que[hd],que[hd+1],getslope(que[hd+1],que[hd]),getk(i));
		while(hd < tl && getslope(que[hd + 1], que[hd]) <= getk(i)) {
			++hd;
		}
		//		printf("%d %d %d %d\n",i,que[hd],hd,tl);
		f[i] = calc(que[hd], i);
		bck[k][i] = que[hd];
		//		printf("%lld?\n",f[i]);
		while(hd < tl && getslope(que[tl - 1], que[tl]) >= getslope(que[tl], i))
			tl--;
		que[++tl] = i;
	}
	return ;
}

int main() {
	// freopen("test.in", "r", stdin);
	// freopen("test.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		sum[i] = sum[i - 1] + a[i];
	}
	for(k = 1; k <= m; ++k) {
		for(int i = 1; i <= n; ++i) {
			f[i] = 0;
		}
		solve();
		//		puts("\nqwq\n");
		for(int i = 1; i <= n; ++i) {
			g[i] = f[i];
		}
	}
	printf("%lld\n", g[n]);
	int nw = n;
	for(int i = m; i >= 1; --i) {
		printf("%d ", bck[i][nw]);
		nw = bck[i][nw];
	}
	return 0;
}