前言：
dp的时候可能会出现一些神仙数据，导致dp部分写出来了，复杂度使人当场去世（
所以说学一下决策单调性优化还是非常有必要的（
比如说，当我们写一道dp题的时候，写了一个状态转移方程：
f[i]=min/max{f[j]+w(i,j)}（此处请忽略w(i,j)究竟是个啥）
打出暴力dp后一看复杂度：O（n²）
再一看题目数据范围：1e5。
（当场崩溃）
关于单调性究竟是个啥
首先我们都知道二分的要求就是要满足单调性。
（如果在一个点x上，如果决策2更好，则所有比x大的状态都是决策2更好；如果x上决策1更好，则所有比x小的状态都是决策1更好）
具体的单调性情况还是得靠题目最后打表打出来的QWQ
比如像现在一个决策求出来的：1111133333
那么，接下来只会可能出现：1111113333344444
绝对不可能出现111113333322222这样的情况的
决策单调性经典判定方法：四边形不等式
w[b,d]+w[a,c]≤w[a,d]+w[b,c]
一、分治优化dp
看标题就可以知道，这种dp题目是可以拿来分治写法的（其实大部分应该都是二分趴）
例题：BZOJ5125 小Q的书架
题目简介：将数列a划分成k段，使得每段内的逆序对最少。(n<=40000,k<=10,a[i]<=n)
思路整理：首先可以得到dp方程：
f[i][j]=min(f[k][j−1]+w(k+1,i))（w表示求出这个区间内的逆序对数）
很显然，单纯的暴力算法是过不了这道题的QWQ
那么我们就需要来看看能不能加点什么优化了。
打个表，发现：哇，w满足四边形不等式
那么接下来：设b[i]为f[i][j]最优决策点，f[i][j]=f[b[i]][j−1]+w(b[i]+1,i)；则b[i−1]≤b[i]。
那么有了这个单调性，我们就可以分治f啦 ，对于区间 [l,r] 的 f，我们考虑确定它的最优决策点所在的区间 [L,R] 。那么我们找出 mid 处的最优决策点 b，根据决策单调性，则区间 [mid+1,r] 的最优决策区间必定为
[b,R] ，而区间 [l,mid−1]的最优决策区间则必定为 [b,p]。然后就可以递归处理了
最后放一下分治优化的代码板子：
void check(int l,int r){ while(L<l)sum-=a[L++]; while(L>l)sum+=a[--L]; while(R<r)sum+=a[++R]; while(R>r)sum-=a[R--]; } void solve(int l,int r,int L,int R){ if(l>r)return; int mid=(l+r)/2,p=L; for(int i=L;i<=min(mid-1,R);i++){ check(i+1,mid); int ans=f[i][now-1]+sum; if(ans<f[mid][now])f[mid][now]=ans,p=i; } solve(l,mid-1,L,p); solve(mid+1,r,p,R); }
二、单调队列优化dp
这种题型就是以前就在noip里出现过的神仙题了QWQ
例题：[noip2017pj] 跳房子
题目简介：给你一个可调整的灵活性g，求最大可获得的分数
思路整理：首先还是弄一个dp方程：
dp[i]=max{dp[j]}+a[i].val （其中(max(1,d-g)<=a[i].set-a[j].set<=d+g)）v
那么我们打个表，发现：
dp [ i ]是由dp[ l - r ) 转移过去的，dp[ l - r )会由于 i 的增加 向右移
因为区间内数据的左边小于它的数据，就没毛线用了
那么写一个单调队列来维护单调队列中下降的序列，就能在转移之前就可以很容易地处理出该区间移动后的最大值是多少。
就可以求啦QWQ
依然是贴个板子：
bool check(int g){ int l=0,r=0,head=0,tail=0; for(int i=1;i<=n;i++){ while(a[i][0]-a[r][0]>=max(一个数,1)){ while(head<tail&&q[tail-1].a<f[r])tail--; q[tail].a=f[r];q[tail++].b=r++; } while(a[i][0]-a[l][0]>一个数){ if(head<tail&&q[head].b==l) if(q[head].a==f[l])head++; l++; } if(head>=tail)f[i]=-INF+a[i][1]; else f[i]=q[head].a+a[i][1]; if(f[i]>=k)return true; } return false; } int slove(int L,int R){ while(L<R){ int mid=(L+R)>>1; if(check(mid))R=mid; else L=mid+1; } return R; }
结语
其实单调性优化dp还有很多种的QWQ，比如像数据结构优化，斜率优化，凸包优化，CMQ优化之类的QWQ，但是我太菜了，现在还不太懂啊QWQ，以后再填坑吧
最后贴个题单：
Luogu P3515 [POI2011]Lightning Conductor
原文：https://www.cnblogs.com/linskyQWQ/p/12676157.html