YZOJ P2021 [APIO2014]sequence

时间限制：2000MS      内存限制：131072KB

难度： $5.7$

• 题目描述

给定一个长度为 $N$ 的非负整数序列 $a$ ，现要把它分割成 $k+1$ 个连续非空的子序列。

每次分割可以选择一段剩余长度超过 $1$ 的序列，并在其中选择一个位置，把它分割成两个连续非空的子序列。这样做可以得到一些 $Bonus$，为分割出的两个新序列中元素和的乘积。

现要找到一种方案，使得经过 $k$ 次分割后，能得到的 $Bonus$ 最多。

• 输入格式

第一行包含两个整数 $n,  k$ ；

第二行包含 $n$ 个非负整数，表示序列 $a$ 。

• 输出格式

第一行包含一个整数，为最大 $Bonus$ 。

第二行包含 $k$ 个 $1$ 到 $n-1$ 的整数，表示最优方案。其中第 $i$ 个数 $x_i$ 表示在该方案中，进行第 $i$ 次操作时，应该选择第 $x_i$ 个数后面的位置，并将这个数所在的序列分成两部分。

如果有多个最优方案，输出其中任意一种即可。

• 样例输入

• 样例输出

• 数据规模与约定

数据满足 $2 \leq n \leq 100000$，$1 \leq k \leq min\{n-1,200\}$ 。

 

 

 

---

 

 

 

套路题，设 $f_{i, k}$ 为割到第 $i$ 个数且已经割了 $k$ 刀时 $Bonus$ 的最大值，计 $sum$ 为 $a$ 的前缀和。

所以 $f_{i, k}=\min\limits_{j=1}^{i-1}\{f_{j, k-1}+sum_j(sum_i-sum_j)\}$ 。

这样就是 $O(kN^2)$ 无法通过本题。

不难发现其实这是一个斜率优化的经典模型。对这个转移方程进行一些处理

$\begin{align} f_{i, k} &=f_{j, k-1}+sum_j(sum_i-sum_j) \\ \underbrace{f_{i, k}}_{b_i} &=\underbrace{f_{j, k-1}-sum^2_j}_{y_j}+\underbrace{sum_i}_{k_i} \cdot \underbrace{sum_j}_{-x_j} \end{align}$

这里的 $k_i$ 和 $x_j$ 都是单调的，直接上单调队列 $O(kN)$ 即可。

值得注意的是，$x_j$ 是递减的，所以判断的时候符号要反过来。