Luogu P3648 [APIO2014]序列分割 题解

Describe

题目链接

你正在玩一个关于长度为 $n$ 的非负整数序列的游戏。这个游戏中你需要把序列分成 $k + 1$ 个非空的块。为了得到 $k + 1$ 块,你需要重复下面的操作 $k$ 次: 选择一个有超过一个元素的块(初始时你只有一块,即整个序列) 选择两个相邻元素把这个块从中间分开,得到两个非空的块。 每次操作后你将获得那两个新产生的块的元素和的乘积的分数。你想要最大化最后的总得分。 对于所有的数据,$2\leq n \leq 100000,1\leq k \leq min\left(n-1,200\right)$。

Solution

考虑$dp$。 设$s_i=\sum_{i=1}^n a_i$,$f_{i,j}$表示前$i$个数,分成$j$块。 由题意可得,$f_{i,j}=max \left( f_{k,j-1}+s_k\times(s_i-s_k) \right)$ 显然,这个式子可以滚存。 我们设$f_i=f_{i,j},g_k=f_{k,j-1}$。 上面那个式子就变成了: $$f_i=max(g_k+s_k\times(s_i-s_k))(0\leq j < k <i )$$ 显然,这个式子可以斜率优化。 设$k$比$j$更优。 $$g_k+s_k\times(s_i-s_k) \ge g_j+s_j\times(s_i-s_j)$$ 化简一下,可得: $$\frac{(g_j-{s_j}^2)-(g_k-{s_k}^2)}{s_k-s_j}\leq s_i$$ 那么维护一个下凸壳即可。(注意分母可能为$0$)

Code

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
#include<bits/stdc++.h>
#define LD double
using namespace std;
int n,k,a[100010],q[100010],pre[100010][210];
long long g[100010],f[100010],s[100010];
inline LD slope(int j,int k){
return s[j]==s[k]?-2000000000.0:(LD)((LD)((g[j]-s[j]*s[j])-(g[k]-s[k]*s[k])))/((LD)(s[k]-s[j]));
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),s[i]=s[i-1]+a[i];
for(int t=1;t<=k;t++){
int l,r;l=r=1;q[1]=0;
for(int i=1;i<=n;i++){
while(l<r&&slope(q[l],q[l+1])<=s[i]) ++l;
f[i]=g[q[l]]+s[q[l]]*(s[i]-s[q[l]]);
pre[i][t]=q[l];
while(l<r&&slope(q[r-1],q[r])>=slope(q[r],i)) --r;
q[++r]=i;
}
for(int i=1;i<=n;i++) g[i]=f[i];
}
printf("%lld\n",f[n]);
for(int i=k,t=n;i>=1;i--) t=pre[t][i],printf("%d ",t);printf("\n");
}