其實單調佇列就是一種佇列內的元素有單調性的佇列，因為其單調性所以經常會被用來維護區間最值或者降低DP的維數已達到降維來減少空間及時間的目的，
每一個答案只與當前下標的前m個有關，所以可以用單調佇列維護前m的個最小值，
考慮如何實作該維護的程序？？
顯然當前下標\(X\)的\(m\)個以前的元素（即下標小于\(X-M+1\)的元素）肯定對答案沒有貢獻，所以可以將其從單調佇列中洗掉，
對于兩個元素\(A\)，\(B\)，下標分別為\(a\),\(b\)，如果有\(A>=B\)&&\(a<b\)那么B留在佇列里肯定優于\(A\)，因此可以將\(A\)洗掉，
維護隊首：如果隊首已經是當前元素的\(m\)個之前，將\(head\)++，彈出隊首元素
維護隊尾：比較\(q[tail]\)與當前元素的大小，若當前元素更優\(tail\)++，彈出隊尾元素，直到可以滿足佇列單調性后加入當前元素，
考慮單調佇列的時間復雜度：由于每一個元素只會進隊和出隊一次，所以為\(O(n)\)，
P1440 求m區間內的最小值
P1886 滑動視窗 /【模板】單調佇列
P3088[USACO13NOV]Crowded Cows S
#include <bits/stdc++.h>
using namespace std;
int a[2000100];
bool b[2000100];
int q[2000100];//陣列模擬佇列，更好除錯
int head=1,tail=0;
int n,m;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++)
{
while(i-q[head]+1>m&&head<=tail)//若頭結點在范圍外
{
head++;//彈出頭結點
}
while(a[i]<a[q[tail]]&&head<=tail)//若當前節點優于尾節點
{
tail--;//彈出尾結點
}
q[++tail]=i;//當前節點入隊
}
return 0;
}
利用單調佇列，可以優化涉及定長連續子區間求最值的線性dp問題
例題
P1725 琪露諾 琪露諾是最強的！！
P1714 切蛋糕
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/30655.html
標籤：C++
上一篇：前綴和
下一篇：P1358 撲克牌