BZOJ 3675.「APIO2014」序列分割

首先易证分割的顺序对答案没有影响((a+b)c+ab=a(b+c)+bc(a + b) c + ab = a (b + c) + bc)。
然后设 Fi,kF_{i,k} 表示前 ii 个数分割了 kk 次的得分。
有转移 Fi,k=max0j<i(Fj,k1+sumj(sumisumj))F_{i,k} = \max\limits_{0 \le j < i} (F_{j,k - 1} + sum_j (sum_i - sum_j)),其中 sumi=j=1iaisum_i = \sum\limits_{j = 1}^i a_i

把第二维滚动,设 fi=Fi,k,gi=Fi,k1f_i = F_{i,k},g_i = F_{i,k - 1},式子变为 fi=max0j<i(gj+sumj(sumisumj))f_i = \max\limits_{0 \le j < i} (g_j + sum_j (sum_i - sum_j))

对于 0k<j<i0 \le k < j < i,设 jj 优于 kk,有

注意特判 sumj=sumksum_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
#include <cstdio>
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 所以省去该步骤。
*/
}