什么是单调队列

单调队列就是元素单调的队列,譬如一个队列中的元素为1,2,3,4,5,6,单调递增,这就是一个单调队列。咱们先看一道单调队列的模板题:poj2823/洛谷P1886
怎么维护单调队列呢?譬如维护一个单调递增的队列,就是要进入一个元素的时候,把队尾小于它的元素统统出队即可。而在例题中,我们还要记录每个元素在原来数组中的下标以确定是否可用,如果已经出了当前窗口,则出队。


代码:


单调队列优化动态规划

例题1:洛谷P1725 琪露诺

链接:走你╭(′▽`)╯
这题就当是单调队列入门啦。
大家都知道$f[i]=max(f[j])+v[i] (i-r<=j<=i-l)$
直接这么dp肯定超时,那么我们可以把$f[i-r]$到$f[i-l]$这一段都扔到单调队列里,然后取队首即可
单调队列一定不能删除还有可能用到的元素,也不能添加暂时不会用的元素,所以我们要确保在用单调队列时,$i-l$加了进去,没有被其后的元素删掉,而其后的东西也没有加进去。
所以就有了代码中的写法
代码:


例题2:UESSTC594我要长高

链接:走你╭(′▽`)╯

这题充满了恶意啊......
容易想到用$f[i][j]$表示第$i$个儿子长$j$这么高的时候的最小损失值(x[i]表示i儿子本来的身高,则:
$$f[i][j]=min(f[i-1][k] + abs(j-k)×c+ (x[i]-j)×(x[i]-j))$$
现在我们分类讨论一下,假如$j>k$:
$$f[i][j]=min(f[i-1][k]+(j-k)×c+(x[i]-j)×(x[i]-j)$$
变形可得:$$f[i][j]=min((f[i-1][k]-k×c)+(j×c+(x[i]-j)×(x[i]-j)))$$
显然前面那一坨可以塞在一个单调队列里来求小于j的情况下的最优k,具体怎么实现看代码吧。然后$j<k$的情况也差不多:
$$f[i][j]=min((f[i-1][k]+k×c)+(-j×c+(x[i]-j)×(x[i]-j)))$$


得到了美妙的代码:

例题3:HDU3401

链接:走你╭(′▽`)╯

题目大意是买股票,第i天买花$ap[i]$元,卖得$bp[i]$元,可以买$as[i]$张或者卖$bs[i]$张,两次交易之间必须间隔$w$天,并且手上最多持有$m$股,求最多赚多少钱。
$f[i][j]$表示第i天持有j股的最多收益,
如果不交易,那么$f[i][j]=f[i-1][j]$
如果买$f[i][j]=f[i-w-1][k]-(j-k)×ap[i]$
如果卖$f[i][j]=f[i-w-1][k]+(k-j)×bp[i]$
(因为不交易的状态已经转移了,所以买和卖只要考虑第$i-w-1$天即可)
然后我们把状态转移方程变形一下,就是
买:$f[i][j]=(f[i-w-1][k]+k×ap[i])-j×ap[i]$
卖:$f[i][j]=(f[i-w-1][k]+k×ab[i])-j×bp[i]$
前面那陀塞单调队列里,处理一下边界,然后就是考虑一下买的数量的问题即可。



例题4:POJ1821

链接:走你╭(′▽`)╯

题目大意:你带着一群工人刷墙,第i个工人被502胶粘在了s[i]号位子上,他由于手臂长度,唯一的刷墙方式是大手一挥,将第s[i]格加上两边的格子共计k个刷好(0<=k<=l[i],刷了就必须刷s[i]格),然后他刷一格要p[i]元的工资。你现在想尽可能多的坑钱,但是反复刷一个格子太明显了是要不得的,求最多可以坑多少钱。
设f[i][j]表示前i个工人刷j个格子(显然工人已经按照站位排好序了),那么:
$$f[i][j]=max(f[i][j-1],f[i-1][j],f[i-1][k]+(j-k)×p[i])$$
分别表示第j面墙不刷,第i个工人自己玩儿去,和一个转移。
于是我们把后面的式子变形,有k的放在一块儿(肯定大家已经会变了吧,$f[i][j]=(f[i-1][k]-k×p[i])+j×p[i]$
不过边界值是很麻烦的,对于可以作为k的值,一定满足$k<s[i]$,对于可以使用第3个方程的j值,一定满足$j>=s[i]$



总结

可以用单调队列优化的dp题在将方程变形后,有一段可以看做不含有当前状态j,只含有前置状态k的一个整体,这个整体可以塞到单调队列里。