根据题意可以得到以下的方程。
\(f_{i, j}\) 表示前 \(j\) 个分成 \(i\) 段的答案。
看到这个典型的 2D/1D, 肯定有很多人要开始大力斜率优化了。
但是这里斜率优化又要推一堆式子,又要担心浮点数误差啥的,式子复杂了万一推错了或者敲错了怎么办?这里介绍以前从未见过的科技,决策单调性分治!
因为决策是单调的,那么我们每次的决策区间就能定下来,把它塞进分治的模板里就好了。
模板大概长这样:
对于这道题,还要加上一维,这一维直接枚举就可以了,因为一定是上一层转移过来的,如果同一层也能转移,那恐怕还得套一层 cdq。
第一次写这种题,居然一遍过,代码留念。
#include <cstdio>
#include <algorithm>
#define int long long
const int N = 100005;
int n, m, sum[N], f[205][N], ans[N], pre[205][N];
void solve(int l, int r, int L, int R, int k) {
if (l > r) return;
int mid = l + (r-l) / 2;
int pos = 0, max = 0;
for (int i = L; i <= R; i++) {
int an = f[k-1][i] + (sum[mid] - sum[i]) * sum[i];
if (an > max) max = an, pos = i;
}
f[k][mid] = max; pre[k][mid] = pos;
solve(l, mid-1, L, pos, k), solve(mid+1, r, pos, R, k);
}
signed main() {
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; i++) scanf("%lld", &sum[i]), sum[i] += sum[i-1];
for (int i = 1; i <= m; i++) solve(1, n, 1, n, i);
for (int now = n, k = m; now; now = pre[k][now], k--) ans[++ans[0]] = now;
std::reverse(ans+1, ans+1+ans[0]);
printf("%lld\n", f[m][n]);
for (int i = 1; i < ans[0]; i++) printf("%lld ", ans[i]);
return 0;
}