动态规划专题(四)——单调队列优化DP

时间:2021-12-27 08:41:51

前言

单调队列优化\(DP\)应该还算是比较简单容易理解的吧,像它的升级版斜率优化\(DP\)就显得复杂了许多。

基本式子

单调队列优化\(DP\)的一般式子其实也非常简单:

\[f_i=max_{j=max(i-t,1)}^{i-1}(s(i)+g(j))\]

其中\(t\)是一个常数,\(s(i)\)是一个只与\(i\)有关的函数,\(g(j)\)是一个只与\(j\)有关的函数,式子中的\(max\)其实也可以替换成\(min\),但这里以\(max\)为例。

由于\(s(i)\)只与\(i\)有关,因此,在\(i\)不变的时候,\(s(i)\)可以看作是一个常数,因此可以将其提出,得到下面这个式子:

\[f_i=s(i)+max_{j=max(i-t,1)}^{i-1}g(j)\]

我们可以考虑用一个队列来存储合法区间,每次将区间头弹出,然后将当前元素插入队列尾。

不难发现,在队列中,如果找到两个位置\(x,y\)满足\(x<y\),则显然\(x\)将先从队列中被弹出。

那么,如果\(g(x)\le g(y)\),则不难发现,无论如何,\(x\)都不可能对后面的元素再造成贡献了,于是就可以直接将\(x\)弹出。

这样操作之后,由于队列里的元素是按编号递增的,因此元素值肯定是单调递减的。

这样一个满足单调性的队列,就是单调队列

状态转移

单调队列优化\(DP\)的状态转移其实非常简单。

通过上面的分析,显然,队列中队头的元素一定是最大/最小的,所以转移如下:

\[f_i=s(i)+g(q_H)\]

几道例题

下面是几道例题:

第一道例题: 【BZOJ2442】[USACO2011 Open] 修剪草坪

这题还是比较板子的。

第二道例题: 【洛谷3084】[USACO2013 Open] 照片

同样是一道比较简单的板子题。

第三道例题: 【BZOJ1855】[SCOI2010] 股票交易

这题就比较复杂了,需要分多种情况讨论,依然可以用单调队列来进行优化。