淺談決策單調性在1D1D動态規劃中的運用

1D1D動态規劃是指狀态數為O(n)，每個狀态的決策數為O(n)，直接求解的複雜度為O(n^2)的動态規劃方程。但這種方程往往都能夠通過一些合理的組織和決策優化到O(n log n)甚至O(n)的。

由于部落客比較弱是以隻分析下面幾種情況（其他的等會了有時間再補）

1.斜率優化

很奇怪我最開始接觸的竟然是這個效率最高的但适用性最窄的優化

具體來講，每一個決策可以看做一個二維平面上的點，某兩個決策的優劣性可以通過他們之間的斜率得出

并且随着決策的不斷進行，我們所用來比較的斜率也是單調變化的

這樣我們就可以把決策點做成一個凸包，用單調隊列維護就可以了

2.CDQ分治

既然我們已經知道了決策時單調的，如果我們一個決定決策的複雜度不高，并且不依賴于其他的決策，那麼我們可以分治進行。

具體來說，我們每次暴力找出mid處的決策點，然後分治左右區間進行，這樣就減少了每次決策的複雜度。

但這種做法的适用性也不高，如果你一個決策的決定依賴于其他決策，那麼就GG了。

3.決策單調性

終于講到我主要想講的東西了

假入我們隻知道最簡單的一個性質，就是決策單調性，那麼我們要怎麼做？

我們先來看一個執行個體：

最開始我們已經确定了1号點的狀态，那麼全局的決策就變成了：

11111111111111（這裡的每個數字表示每個點的決策點）

那麼我們就可以得出2号點的狀态，接着它對全局的影響：

11111111222222

接下來3号點的狀态我們也可以得出，假如它對全局的影響是

11111111222222

33333333333

我們可以發現，最終我們的全局決策會變為：

11133333333333

就是決策2已經沒有用了！

那麼我們的做法也就出來了，維護一個隊列，維護目前的每一個決策，相鄰的兩個決策所能控制的區間相接。

那麼我們從隊尾往前依次比較每一個決策點，如果目前決策在全局看來都比隊尾決策優，那麼隊尾決策就是沒有用的，出隊。

否則我們就要二分一個轉折點，表示從這個轉折點開始，新決策比隊尾決策優，然後将新決策入隊。

這樣我們就做到O(n log n)來維護每一個決策點對于全局的影響。

注意如果隊頭能影響的區間已經決策完了，那麼隊頭出隊。