單調隊列可以有兩種操作:
1.插入新元素。從隊列末尾到隊列頭搜索元素，找到合適的位置插入，如果這個位置有元素就替換掉。
2.在這個過程中，從團隊領導那裏刪除不符合當前需求的元素。
單調隊列實現起來既簡單又復雜。壹個簡單的數組，壹個頭和壹個尾指針就可以了。復雜的雙向鏈表。
使用:
1，保存最優解，次優解等。
2.用單調隊列優化dp方程，可以把O(n)的復雜度降低到O(1)。換句話說，本來要超時的N維dp降優化到N-1維才能通過。這也是我想記錄的壹點。
使用單調隊列可以優化任何DP嗎？答案是否定的。
記住！只有形式DP [I] = max/min (f [k])+g [I] (k
優化的對象是f[k]。
通過事例加深感情。
/problem.php？pid=1685
我想長高
描述
韓服有n個兒子，分別是韓壹、韓二……韓n，由於韓家人深厚的演技和密切的配合，演出大獲成功，票房甚至達到了2000萬。周子是壹個很有威望的人，但他表面上很幹凈，但實際上，他的內心是黑暗的。當他看到韓國家庭的繁榮時，他變得嫉妒，他對兩個韓國人站成壹排時的不均勻高度發表了謙虛的言論。由於周子的影響，隨便壹句話就會給韓國家庭造成巨大損失。具體損耗計算如下:韓壹，韓二…韓N站成壹排，損耗為C*(韓壹和韓壹的身高差+1 (1
投入
有幾組數據，壹直處理到文件結束。每組數據的第壹行是兩個整數:漢字數n (1
首先方程成立，很容易認為dp[i][j]代表第I個兒子的身高成本最低。很容易知道現任兒子的身高成本只受前任兒子的影響。因此，
DP[I][j]= min(DP[I-1][k]+ABS(j-k)* C+(x[I]-j)*(x[I]-j))；其中x[i]是第I個兒子的原始高度。
我們來分析壹下復雜程度。
首先，有n個兒子，這需要壹個周期。而且每個兒子的身高都是0到100，同樣需要壹維。此外，從0到100的每個高度都可以從前壹個兒子從0到100的高度遞歸導出。
所以樸素算法的時間復雜度是O (n 3)。題目只給了兩秒鐘，不能接受！
分析方程:
當第I個兒子的身高高於第i-1個兒子的身高時，
DP[I][j]= min(DP[I-1][k]+j * C-k * C+X)；(k & lt=j)其中X=(x[i]-j)*(x[i]-j)。
當第I個兒子的身高比第i-1個兒子的身高矮時，
DP[I][j]= min(DP[I-1][k]-j * C+k * C+X)；(k & gt=j)
對於第壹個方程，設f[I-1][k]= DP[I-1][k]-k * c，g[I][j]= j * c+x；所以DP[I][J]= min(F[I-1][K])+G[I][J]。在這種形式下，我們可以用單調的隊列進行優化。
第二個等式是壹樣的。
接下來就是如何實現了，有點棘手。詳見下文。
查看代碼
另壹個適合理解這種優化方法的題目是HDU 3401/showproblem.php？pid=3401
總的題目是:壹個人知道未來T天的股市，想知道最後能賺多少錢。
建倉狀態dp[i][j]表示妳在第I天擁有J只股票時賺了多少錢。
狀態轉換包括:
1.前壹天我沒有買入或賣出:
dp[i][j]=max(dp[i-1][j]，dp[i][j])
2.從i-W-1天前買壹些股票:
dp[i][j]= max(DP[I-W-1][k]-(j-k)* AP[I]，DP[I][j])
3.從i-W-1天賣出部分股票:
dp[i][j]= max(DP[I-W-1][k]+(k-j)* BP[I]，DP[I][j])
這裏需要解釋壹下為什麽只考慮i-W-1日的買賣情況。想壹想，i-W-2可以通過不買不賣的方式把自己的最佳狀態轉移到第壹個i-W-1日嗎？以此類推，前面的不需要考慮，只考慮i-W-1天的情況。
對購買股票的情況進行分析，轉化為適合單調排隊優化的方程。
DP[I][j]= max(DP[I-W-1][k]+k * AP[I])-j * AP[I].設F[I-W-1][K]= DP[I-W-1][K]+K * AP[I]，則DP [I] [J] = Max (F [I-W-1] [
這可以用單調隊列來優化。賣股的情況也差不多。
查看代碼
最後說壹個應用，用單調隊列優化多背包問題hdu 2191。
如果有n件物品，每件物品的價格是W，每件物品的重量是C，每件物品的數量是K，那麽就用壹個容量為M的背包裝滿這樣的物品，使背包的價值最大化。這個問題就是多重背包問題。
對於多重背包問題，壹種優化方法是使用二元優化，這種優化方法的時間復雜度為O(m*∑log k[i])，如所示。
blogs . com/ka 200812/archive/2011/08/06/2129505 . html
單調排隊優化的復雜度為O(mn)。
首先，對於第I條，如果體積為V，數值為W，數量為K，那麽當前體積J可分為V組(0，1，...V-1)根據v的余數。
對於任意壹個基團，可以得到轉移方程:f[i*V+c]=f[k*V+c]+(i-k)*W，其中c是V個基團中的任意壹個。
設f[i*V+c]=dp[i]，則我們得到DP[I]= DP[k]+(I-k)* W(k & gt；=i-K)
如果把dp[k]-k*W看作壹個優化函數，那麽可以用單調隊列進行優化。