题目链接

【APIO2014】序列分割

题目描述:

你正在玩一个关于长度为 n 的非负整数序列的游戏。这个游戏中你需要把序列分成 k + 1 个非空的块。为了得到 k + 1块,你需要重复下面的操作 k 次:

选择一个有超过一个元素的块(初始时你只有一块,即整个序列)

选择两个相邻元素把这个块从中间分开,得到两个非空的块。

每次操作后你将获得那两个新产生的块的元素和的乘积的分数。你想要最大化最后的总得分。

输入输出格式

输入格式:

第一行包含两个整数 $n$ 和 $k$。保证 $k + 1 \leq n$。
第二行包含 $n$ 个非负整数 $a_1, a_2, \cdots, a_n (0 \leq a_i \leq 10^4)$,表示前文所述的序列。

输出格式:

第一行输出你能获得的最大总得分。

第二行输出 $k$ 个介于 $1$ 到 $n - 1$ 之间的整数,表示为了使得总得分最大,你每次操作中分开两个块的位置。第 $i$ 个整数 $s_i$ 表示第 $i$ 次操作将在 $s_i$ 和 $s_{i + 1} $之间把块分开。

如果有多种方案使得总得分最大,输出任意一种方案即可。

输入输出样例

输入样例#1:

7 3
4 1 3 4 0 2 3

输出样例#1:

108
1 3 5

说明

你可以通过下面这些操作获得 $108$ 分:

初始时你有一块 $(4, 1, 3, 4, 0, 2, 3)$。在第 $1$ 个元素后面分开,获得 $4 \times (1 + 3 + 4 + 0 + 2 + 3) = 52$ 分。

你现在有两块 $(4), (1, 3, 4, 0, 2, 3)$。在第 $3$ 个元素后面分开,获得 $(1 + 3) \times (4 + 0 + 2 + 3) = 36$ 分。

你现在有三块 $(4), (1, 3), (4, 0, 2, 3)$。在第 $5$ 个元素后面分开,获得 $(4 + 0) \times (2 + 3) = 20$ 分。

所以,经过这些操作后你可以获得四块 $(4), (1, 3), (4, 0), (2, 3)$ 并获得 $52 + 36 + 20 = 108$ 分。

限制与约定

第一个子任务共 $11$ 分,满足 $1 \leq k < n \leq 10$。

第二个子任务共 $11$ 分,满足 $1 \leq k < n \leq 50$。

第三个子任务共 $11$ 分,满足 $1 \leq k < n \leq 200$。

第四个子任务共 $17$ 分,满足 $2 \leq n \leq 1000, 1 \leq k \leq \min{n - 1, 200}$。

第五个子任务共 $21$ 分,满足 $2 \leq n \leq 10000, 1 \leq k \leq \min{n - 1, 200}$。

第六个子任务共 $29$ 分,满足 $2 \leq n \leq 100000, 1 \leq k \leq \min{n - 1, 200}$。

题解

在解决这个问题之前,我们先大胆口胡一个结论:分割的顺序不影响最后的结果。
接下来就是这个结论的证明了:
设两次分割把队列分为了A,B,C三个部分。

  1. 先分割A,B之间,再分割B,C之间:$ans=A(B+C)+BC=AB+AC+B*C$
  2. 先分割B,C之间,再分割A,B之间:$ans=C(A+B)+AB=AB+AC+B*C$

由此可以得出分割的顺序不影响最后的结果。
接下来我们就可以进行dp了。
这是一个很明显的二维dp。
$dp[i][k]$表示前$i$个数被分割了$k$次所能得到的最大的答案。
转移方程为$dp[i][k]=max(dp[j][k-1]+\sum_{u=1}^{j}a[u]\sum_{u=j+1}^{i}a[u])$(在第$k$个数和第$k+1$个数之间分割)
证明:
假设$dp[j][k-1]$最右边的分割点为$o$和$o+1$(从$j$转移后$dp[i][k]$最后),
则$dp[i][k-1]=dp[j][k-1]+\sum_{u=1}^{o}a[u]
\sum_{u=j+1}^{i}a[u]$
所以$dp[i][k]=dp[i][k-1]+\sum_{u=o+1}^{j}a[u]\sum_{u=j+1}^{i}a[u]$
$=dp[j][k-1]+\sum_{u=1}^{o}a[u]
\sum_{u=j+1}^{i}a[u]+\sum_{u=o+1}^{j}a[u]\sum_{u=j+1}^{i}a[u]$
$=dp[j][k-1]+\sum_{u=1}^{j}a[u]
\sum_{u=j+1}^{i}a[u]$
接下来我们用前缀和减小时间复杂度,
设$sum[i]=\sum_{j=1}^{i}a[j]$
所以$dp[i][k]=max(dp[j][k-1]+sum[j]*(sum[i]-sum[j]))$
这个转移方程时间复杂度为O(n^2),因为$2 \leq n \leq 100000$所以我们用斜率优化。

重点:
我们取$j$,$p$满足 $p<j<i$且$j$比$k$更优,那么有如下不等式:
$$dp[j][k-1]+sum[j](sum[i]-sum[j])>dp[p][k-1]+sum[p](sum[i]-sum[p])$$
化简后得:
$$\frac{(dp[j][k-1]-sum[j]^2)-(dp[p][k-1]-sum[p]^2)}{sum[p]-sum[j]}\leq sum[i]$$
接下来维护一个下凸壳就可以了。
注意:题目中$a[i]$的范围是非负整数,所以$a[i]$可以为0,计算时需要特判。
上代码:

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
#include<bits/stdc++.h>
#define inf 1e18
using namespace std;
int n,k;
long long a[100009],s[100009];
long long dp[100009];
long long pp[1000009],g[100009];
long long l=1,r=1;
double js(int j,int k){
if(s[j]==s[k]) return -inf;
return 1.0*(g[k]-g[j]+s[j]*s[j]-s[k]*s[k])/(s[j]-s[k]);
}
int main(){
scanf("%d%d",&n,&k);
for(int j=1;j<=n;j++)
scanf("%lld",&a[j]);
for(int j=1;j<=n;j++)
s[j]=s[j-1]+a[j];
for(int o=1;o<=k;o++){
l=1;r=1;
pp[1]=0;
for(int j=1;j<=n;j++){
while(l<r && js(pp[l+1],pp[l])<s[j]) l++;
dp[j]=g[pp[l]]+(s[j]-s[pp[l]])*s[pp[l]];
while(l<r && js(pp[r],pp[r-1])>js(j,pp[r])) r--;
pp[++r]=j;
}
for(int j=1;j<=n;j++)
g[j]=dp[j];
}
printf("%lld",dp[n]);
return 0;
}

最后更新: 2019年09月27日 19:22

原始链接: http://oierlin.cf/2019/07/19/【APIO2014】序列分割/

× 请我吃糖~
打赏二维码