优化单调队列使用单调队列优化的主题具有这样的特征。 他需要维持随着遍历顺序而变化的区间内的某个最佳值。 但是，其变化一定具有维持区间的左右端点一定会单调增加，不会发生回流现象的特性。 否则，在保持队列单调性的过程中被剪枝的数据可能是新区间中的最大值。
作为维持区间最佳值的方法，有静态算法ST算法、动态更新区间最高值的段树等，但对于区间左端点或右端点不单调增加的区间最高值问题，必须只使用段树优化，不使用单调队列。 根据该特性，也可以迅速判断用哪种方法优化DP问题。
观察待维持区间左右端点的变化趋势，如果发现左右端点随逐步增加而增加，则可以选择用单调队列优化其DP问题。
对于某个DP问题，如果不知道该如何优化，我们可以先写下那个朴素条件下的状态转移方程，根据朴素状态下的状态转移方程进行变化，找到符合单调队列优化公式的，就知道在单调队列中需要保持什么
当然，不用看问题就知道，单调队列中必然维持的是状态中的某一维下标，但如何顺序维持这些下标，是我们变化的目标。 通常，在使用单调队列优化问题中，该状态转移方程式中一定存在这样的状态转移方程式：
这里，l和r都随着I的增加而单调增加(能够维持原始值但不能减少)，而f ) DP[j]表示前一级的函数，在该区间内的最大值实时维持即可。 r增加时需要在队列中插入元素，l增加时需要删除队列末尾的非法元素。 这样，队列的末尾总是维持区间[l]
例题围栏
//在一块板上最多可涂抹一次# include bits/stdc.husingnamespacestd； int dp[110][16010]； vectorvectorint arr； intcalc(intI，int k ) { return dp[i-1][k]-arr[i][1]*k； (}int main ()/(先举出朴素的DP方式) /因为相同的板至多被涂抹了一次，所以表示不同板之间的碰撞关系(/这样只能以板的数量为阶段进行DP； //同时，我们必须按区间排列所有的粉刷匠。 否则，最高质量的int n，m； scanf('%d%d )，n，m )； arr=向量int (3(m1，向量int )3)； for(intI=1； i=m； I )扫描(' % d % d )、arr[i][0]、arr[i][1]、arr[i][2]； }sort(arr.Begin )、arr.end )、[ (矢量inta，矢量intb ) { return a[2]b[2]； )； //写出朴素的DP方程memset(DP，0，sizeof ) DP )； for(intI=1； i=m； I ) { dequeint deq； for(intk=max(0，arr[i][2]-arr[i][0] )； karr[i][2]； (k )//对之前使用的一部分进行预处理后进行for )； deq.empty(calc ) I，k )=calc(i ) I，deq.front ) )； deq.pop_front ()； dq.push_front(k； }for(intj=1； jn 1； j ) (/第I个工人可以选择不打磨dp[i-1][j]=max ) DP[I][j]，dp[i-1][j] )。//第j张板子可以选择不打磨DP[I][j]=max(DP[I][j]，dp[i][j-1] )。//第I个人油漆时的转移方程if (j=arr [ I ] [2] jarr [ I ] [2] arr [ I ] [0] ) for )； deq.empty(deq.back ) j-arr[i][0]； deq.pop_back ()； DP[I][j]=max(DP[I][j]，calc(I，deq.back ) ) arr[i][1]*j )； } } } coutdp[m][n]endl； 返回0； )例题裁剪序列
# include bits/stdc.husingnamespacestd； 常数int n=100050； 龙龙龙龙
g dp[N],vise[N];//用于懒惰标记int deq[N],p[N],A[N];long long n,m;//使用小根堆的技巧，插入相反数priority_queue<pair<long long,int>> que;int main(){ scanf("%lld %lld",&n,&m); long long arr[n+1]; for(int i=1;i<=n;i++){ scanf("%lld",&arr[i]); if(arr[i]>m){ cout<<-1<<endl; return 0; } } long long sum=0; int head=0; int tail=-1; int pre=1; //单调队列获得一段区间中的最值，不需要使用线段树，ST时间复杂度线性。 for(int i=1;i<=n;i++){ sum=sum+arr[i]; for(;sum>m;pre++)sum=sum-arr[pre]; p[i]=pre-1; for(;tail>=head&&deq[head]<pre;head++); for(;tail>=head&&arr[deq[tail]]<=arr[i];tail--); deq[++tail]=i; //先插入再更新 A[i]=arr[deq[head]]; } head=0; tail=-1; sum=0; pre=1; for(int i=1;i<=n;i++){ //贪心更新，尽可能使得当前这一段区间的长度够大 dp[i]=dp[p[i]]+A[i]; //维持arr[i]的下标递增，值递减的单调队列，注意区间右端点我们可以用之前求解的p快速获得 for(;tail>=head&&deq[head]<p[i]+1;head++)vise[deq[head]]=0; for(;tail>=head&&arr[deq[tail]]<=arr[i];tail--)vise[deq[tail]]=0; deq[++tail]=i;//先将该元素插入队列 //更新优先级队列，只有单调队列中元素超过两个时才可以更新 if(tail>head){ que.push({-dp[deq[tail-1]]-arr[deq[tail]],deq[tail-1]}); vise[deq[tail-1]]=-dp[deq[tail-1]]-arr[deq[tail]]; } //根据惰性删除，删除优先级队列中已经失效的值。 for(;!que.empty()&&(vise[que.top().second]!=que.top().first||vise[que.top().second]==0);que.pop()); if(!que.empty())dp[i]=min(dp[i],-que.top().first); } cout<<dp[n]<<endl; return 0;}分析
相当棒的一道例题，可以让我们更为细致地理解如何使用单调队列，为什么使用单调队列，当区间动态变化时，我们可以使用单调队列+优先级队列的方式优化时间复杂度，当然本题实际上也可以利用线段树求解，考虑到每一个元素至多进入和离开单调队列一次，这样我们就可以在元素离开单调队列时，更新线段树中的值为无穷大，更新时使用线段树查询即可。
这道题的特点是并不存在直观地可以用优先级队列进行优化的方法，这需要我们借助其他结构解决该问题，我们也要学会合理地利用各种数据结构，得到想要的结果。
多重背包问题
#include<bits/stdc++.h>using namespace std;const int N=20010;int dp[N],pre[N],q[N];int n,m;int main(){cin>>n>>m;for(int i=0;i<n;i++){memcpy(pre,dp,sizeof(dp));//关键点，将i-1个物品处理的最优值保存到pre中 int v,w,s;scanf("%d %d %d",&v,&w,&s);for(int j=0;j<v;j++){int head=0; int tail=-1;for(int k=j;k<=m;k+=v){ //固定长度的区间，所以每次至多删除一个元素，我们无需使用循环 //单调队列固定三步，删除队头超出区间的元素if(head<=tail&&k-s*v>q[head]){//新的元素 ++head; }//剪枝队头不合法元素while(head<=tail&&pre[q[tail]]-(q[tail]-j)/v*w<=pre[k]-(k-j)/v*w)--tail;//入队//状态转移if(head<=tail){dp[k]=max(dp[k],pre[q[head]]+(k-q[head])/v*w);}//添加元素q[++tail]=k;}}}cout<<dp[m]<<endl;return 0;}分析
本题是一道非常好的单调队列优化的题目，这里用到很多实用的编程技巧，首先为了降低时间复杂度，我们抛弃实用双端队列，而是用一个数组模拟单调队列，用数组模拟单调队列，我们需要保证插入元素在队尾，而删除元素在队头，否则会发生数组越界的问题。
除此之外就是分析问题了，也即确定我们用什么大小关系来维持一个单调队列，值的注意的是，单调队列中一定维持的是体积这一维度的下标，并且维持的元素大小只与这一下标有关，而不与其他下标产生关联关系。
本题中，当我们按照体积取余后，发现不同的背包大小之间，只有相差体积大小为第i个物品大小时，才会发生转移，其他相互不影响，所以我们可以将整个背包大小，按照第i个物品的体积大小分割成不同的余数，余数相同的一组背包体积之间可以相互转化，其他不能转化。
这时我们就可以发现:
从状态转移方程中我们可以看到，实际上我们需要维持长度不超过s的一段连续同余元素中的一个关于公式：
上面这个式子中实际上只有k是变量，i-1是阶段，在这一层循环中始终不变，而j则是与所求体积有关的下标，在求解上式是是一个定值，也即在求解体积为j的背包的最优值时，上式的变量只有k，而k指的是一段区间中使得上式取的最大值的k，区间的左右端点都是单调递增的，所以我们可以用单调队列来维持这一段区间中上式的最大值的下标，这样我们就可以将时间复杂度优化到O(mn)。