前言
单调队列优化\(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] 股票交易
这题就比较复杂了，需要分多种情况讨论，依然可以用单调队列来进行优化。