[BZOJ3675/Luogu3648][Apio2014]序列分割(动态规划,斜率优化)

发布于 2018-02-01  137 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3675/Luogu3648][Apio2014]序列分割(动态规划,斜率优化)

Description

小H最近迷上了一个分隔序列的游戏。在这个游戏里,小H需要将一个长度为n的非负整数序列分割成k+1个非空的子序列。为了得到k+1个子序列,小H需要重复k次以下的步骤:
1.小H首先选择一个长度超过1的序列(一开始小H只有一个长度为n的序列——也就是一开始得到的整个序列);
2.选择一个位置,并通过这个位置将这个序列分割成连续的两个非空的新序列。
每次进行上述步骤之后,小H将会得到一定的分数。这个分数为两个新序列中元素和的乘积。小H希望选择一种最佳的分割方式,使得k轮之后,小H的总得分最大。

Http

BZOJ
Luogu

Tag

动态规划,斜率优化,单调队列

解决思路

首先需要知道的是,如果分割的位置是一定的,那么最后的和也是一定的。
比如说\(ab|cd|e\),先分割前面和先分割后面是一样的,推广一下,分割成\(K\)个块的答案就是把每一个块求和再两两乘起来求和。
那么考虑\(DP\),设\(F[i][k]\)表示前\(i\)个数分割\(k\)次最大的得分,那么枚举一个小于\(i\)的\(j\)就有
\[F[i][k]=max(F[j][k]+Sum[j]*(Sum[i]-Sum[j])\]
其中\(Sum[i]\)是前\(i\)个数的前缀和。
这样的复杂度是\(O(n^2k)\)的。考虑斜率优化消去一维。
设\(j_1 < j_2\),并且\(j_2\)的答案更优,那么有
\[F[j_1][k-1]+Sum[j_1]*Sum[i]-Sum[j_1]^2 < F[j_2][k-1]-Sum[j_2]*Sum[i]-Sum[j_2]^2\]
\[F[j_1][k-1]-Sum[j_1]^2-F[j_2][k-1]+Sum[j_2]^2 < Sum[i]*(Sum[j_2]-Sum[j_1])\]
那么这样就可以用单调队列维护了。注意,因为数是非负整数,所以\(Sum[j_2]-Sum[j_1]\)可能是0,不能除过去。
\(Luogu\)需要输出方案,那么在转移的时候再记录一下从哪里分割转移过来即可。

代码

\(BZOJ\)

\(Luogu\)

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3675/Luogu3648][Apio2014]序列分割(动态规划,斜率优化)


HNCJ OIer