單調隊列優化

前言

接下來的幾個章節會跟 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 的形式的話那麼也可以使用單調隊列優化(多重背包就是一個例子)。有時候改變枚舉順序他也會變成單調隊列。

Last updated 3 years ago

Was this helpful?