动态规划专题(五)——斜率优化DP

前言

斜率优化\(DP\)是难倒我很久的一个算法,我花了很长时间都难以理解。后来,经过无数次的研究加以对一些例题的理解,总算啃下了这根硬骨头。

基本式子

斜率优化\(DP\)的式子略有些复杂,大致可以表示成这样:

\[f_i=min_{j=1}^{i-1}(A(j)-B(j)*S(i)+C(i))\]

其中\(A(j)\)\(B(j)\)是两个只与\(j\)有关的函数,\(S(i)\)\(C(i)\)是两个只与\(i\)有关的函数,式子中的\(min\)其实也可以替换成\(max\),但这里以\(min\)为例。

不难发现,如果只有\(A(j)\)\(C(i)\)两项,就是单调队列优化\(DP\)的基本式子了。

但是,由于式子中含有\(B(j)*S(i)\)这一项既与\(i\)相关,又与\(j\)相关的式子,就不能直接用单调队列,而要进行一定转化了。

考虑将\(A(j)\)移到等号左边,并将\(f_i\)移到等号右边,则原式可以转化成这样:

\[A(j)=B(j)*S(i)+(f_i-C(i))\]

注意,在\(i\)不变的时候,我们可以将只与\(i\)有关的项看成常数项。

于是,这个函数就可以看作一条直线,其中\(S(i)\)就相当于这条直线的斜率,而\(f_i-C(i)\)就相当于这条直线的截距

\(C(i)\)是固定的,因此,如果要让\(f_i\)最小,则应让\(f_i-C(i)\)最小,对应到图像中就是让截距最小。

那么应如何让截距最小呢?

大致思路

首先,我们可以想象有一条斜率固定的直线(我太懒,不想画图… …),然后图上有若干个点,现在要用这条直线从图的最下方往上慢慢移动,直至碰到第一个点,而这个点就是我们要找的最优点。

则不难发现,如果连续的三个点呈上凸状,则无论该直线斜率取多少,碰到的第一个点都不可能是中间这个点。

换句话说,就是中间这个点对答案没有任何贡献了。

于是就有一个策略:当我们要加入一个新的点时,比较当前点与前一个插入的点\(S_1\)、前一个插入的点与倒数第二个插入的点的斜率\(S_2\),如果\(S_1\le S_2\),则可将前一个插入的点弹出。

重复此操作,直至\(S_1>S_2\)或图上只剩一个点,然后将当前点插入。

如何求最优解

但是,这样一来,我们好像还是没能求出最优解。

此时又有两种操作方式:在凸包上二分单调队列维护最优解

对于某些问题,它可以确保决策单调性,即一个点如果当前不是最优解,则以后都不可能是最优解了。这样的问题可以直接用单调队列来维护最优解。

但有些问题却不一定满足这种性质,此时就需要在凸包上二分最优解了,但依然需要用单调队列来维护点集。

所以,如果你不会单调队列,最好赶紧去研究一下,然后再学习斜率优化\(DP\)

几道例题

第一道例题: 【BZOJ2726】[SDOI2012] 任务安排

听说是入门题?洛谷上的弱化版可以直接单调队列维护,但是\(BZOJ\)上存在负数,需要在凸包上二分。

第二道例题: 【CF311B】Cats Transport

一眼看上去像是\(WQS\)二分,其实题意转换后可以直接斜率优化。

第三道例题: 【洛谷3648】[APIO2014] 序列分割

一开始觉得是区间\(DP\),结果一看数据范围,推了波性质,才发现其实可以用斜率优化\(DP\)来做。

转载于:https://www.cnblogs.com/chenxiaoran666/p/SlopeDP.html