YZOJ P2021 [APIO2014]sequence

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\) 是递减的,所以判断的时候符号要反过来。

 

 

 

 

 

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注