單調隊列優化

前言

接下來的幾個章節會跟 1D/1D DP 有關，這邊給出 1D/1D DP 的一般型式：

$dp(i)=\max\limits_{l(i)\leq j\leq r(i)}\{dp(j)+w(i,j)\}$

接下來的章節可能會多次使用到這個論述，如果忘記了可以回來看。

概述

理論

有一些 1D/1D 的 DP 的轉移式會長成下面這樣：

$dp(i)=h(i)+\max\limits_{l(i)\leq j\leq r(i)}\{A(j)\}$

其中$A(j)$是一個可能包含$dp(j)$的函數，$h(i)$是一個可以快速求出來的函數。並且滿足$l(i),r(i)$皆為遞增函數，並且有$r(i)<i$。

那麼我們就可以發現轉移式取 max 的地方就是在做區間最大值。那麼我們其實可以直接套線段樹解掉這個 DP。但這還不夠好。

由上面的敘述我們知道$l(i)$跟$r(i)$都是遞增的，有一個特別的資料結構可以均攤$O(N)$的處理這個問題：單調隊列

單調隊列

單調隊列是一種資料結構，他可以維護一個往同一個方向移動的區間(也就是)的最大/小值。

因為我很懶，而且單調隊列是一個相對常見的概念，這邊我先丟一個連結 OI wiki 單調隊列 。未來如果我心血來潮的話會回來補他。

決策單調性

如果忘記決策單調性是什麼的請回到 DP OPT Time 的介紹

在進行單調隊列的過程中，我們可以發現他的最優決策點是遞增的，而這也是這個做法之所以會是$O(N)$的原因。因為最優決策點永遠只會一直增加而不會減少，最終最優決策點最多就只會掃過$N$個數字。

於是這裡有一個小結論：

對於一個 1D/1D DP 而言，如果$w(i,j)$可以被分解成 只有$i,j$的項的函式相加的話，那麼就可以套用單調隊列優化。

總結

要注意的是，通常在做的過程中 DP 是多維的，但是如果可以把其他維度固定讓每次轉移都變成 1D/1D 的形式的話那麼也可以使用單調隊列優化(多重背包就是一個例子)。有時候改變枚舉順序他也會變成單調隊列。

題目

1. cses 1644
2. 有限背包
3. CF 372C
4. TIOJ 1841 (還沒做)
5. NOI 2011 NOI嘉年華 (還沒做)