DP OPT Time

動態規劃優化時間

介紹

DP 優化種類繁多，礙於 iceylemon 能力薄弱，這裡只列出一些我知道的 DP 優化。下面的優化大致上有按難度排。

1. 前綴和優化

2. 矩陣快速冪優化

3. 資料結構優化

4. 單調隊列優化

5. SOS 優化

6. 斜率優化 (Convex Hull Trick)

7. 四邊形優化

8. 分治優化

9. Aliens 優化

10. Slope Trick (不難，但是很冷門)

在普通的 DP 中我們遇到轉移式裡面有 max 或是 min 的東西我們常常都是暴力的把所有子問題都算出來。不過有時候我們可以利用一些題目性質，讓我們不需要把所有的子問題算出來就可以得到轉移。也就是說，有時候我們可以利用題目性質在小於暴力枚舉的時間內得到我們要的轉移來源(轉移點/決策點)。這也幾乎是 DP 優化的共同概念，也就是優化轉移時間。

一些定義

DP 的表示方式

為了接下來方便說明，我們定義 xD/yD DP 的意思是狀態數有 $O(n^x)$種且轉移複雜度為$O(n^y)$的 DP 。而這類 DP 未經優化的複雜度通常是$O(n^{x+y})$。

(最優)決策點

最優決策點這個名詞是出現在最佳化的 DP 問題。當你在進行轉移的時候，可以選擇的$j$值叫做決策點(或稱轉移點)，而取到的最小/大值的位置就稱為最優決策點。

決策單調性(1D/1D)

對於一個 1D/1D DP：$dp(i)=\max\{dp(j)+w(i,j)\}$

令$p_i$為$dp(i)$取到最小值時$j$的值，也就是$p_i$是$dp(i)$的決策點。如果$p$是單調遞增(減)的，那麼我們就說$dp$有決策單調性。