前言：dp蒟蒻拼命挽救一下dp a....，会围绕三个“形如”来写...但更重要的是本质理解啊qwq

A.单调队列优化：

有时状态转移方程形如f[i][j]=min{f[i-1][k]}+w(i,j)，其中l(i,j)<=k<=j，l(i,j)<=l(i,j+1)。如果两个决策k1,k2满足f[i-1][k1]<=f[i-1][k2]且k1>k2，那么k1出现后k2就没用了。维护一个队列，按k从小到大存下所有有用的决策，f[i-1][k]是单调上升的。每次加入新决策时，从队列末尾删去没用的决策。当队列开头决策的k<l(i,j)时将它删去。（emmmmmmm这个海星，在单调性满足情况下用单调队列留下靠后的且较优的）

B.决策单调性优化：

首先对于所有的疑似决策单调性优化的题，最好是用打表来证明（随便搞个大样例或者后头对拍一下.....一般严谨证明不太现实，当然也可以）这个在打O（N^2⁺）暴力时顺便记录一下gi就行了（这里gi指是从gi转移到i的）[最好考试都要先打好暴力，然后对着暴力来想a，分析性质]

这里主要介绍两种实现：

1.二分实现：

首先是讲稿上的一些说法：

有时状态转移方程形如f[i]=min{f[j]+w(j,i)}，其中j<i。记g(i)表示f[i]取到最优值时的决策点j，如果g(i)<=g(i+1)，我们可以用单调性优化dp。同样用一个单调队列存下有用的决策，对于相邻两个决策k1<k2，我们二分求出k2比k1优的时间t(k1,k2)。加入一个新决策时，假设新决策为k3，末尾两个决策为k1,k2。如果t(k2,k3)<=t(k1,k2)，那么可以删去k2。转移时如果开头的决策已经不优了就删去它。

接下来补充一点自己理解的具体实现：

首先，对于所以的gi可以先标记为1（0）[视题目而定]默认为全都为从1转移过来的，这里用一个结构体的栈来维护每个单调决策的适用范围。

然后，我们依次考虑往后的单调决策更新，那么对于每个i我们先通过二分已经维护的单调决策的适用范围可以算出f[i]（用线段树啥的来刷一遍gi有点太傻了a....）同时由此我们可以得出复杂度为O（nlogn）（因为二分嘛）。

现在我们得到了新的f[i]，所以用它来更新以后的，由于单调性，我们可以从后往前扫描栈，这里有两种情况：

$(1)$ ;

这里每个决策里的二分就是对于当前的m判断f[i]+w[i,m]和f[j]+w[j,m]谁更优，若更优则i的起始范围往前移，否则往后移；

感觉这个二分实现还挺好想的a....（雾）而且适用范围貌似要比分治实现更广一些（听分治实现的时候一脸懵a...）

在这里推荐一道例题（实打代码才有效）

bzoj4709: [Jsoi2011]柠檬

以及代码（咕咕咕）：

2.分治实现：

首先依旧是讲稿上的一些说法：

有时状态转移方程形如f[s][i]=min{f[s-1][j]+w(s,j,i)}，其中j<i，且g(s,i)<=g(s,i+1)。如果w(s,j,i)不能很快算出，之前的方法就不再适用了。假设i的取值范围是[l,r]，取m=(l+r)/2。我们可以先求出g(s,m)，然后递归处理[l,m-1]和[m+1,r]。

接下来依旧是补充一点自己理解的具体实现：

（咕咕咕）

秒客网

单调队列优化和决策单调性优化