大佬們要讓蒟蒻給他們講斜率優化 …….（色色發抖

斜率優化是什么呢，先看點沒用的東西。
考慮一類動態規劃，滿足這樣的性質：
狀態數有n個，一個狀態的決策數有n個
形似f[i]=♂i1f[j]定義♂為亂七八糟的運算
這樣的dp有什么好的性質呢？？？

首先考慮這樣一種 子類型

f[i]=mini?1j=1f[j]+w[j,i]

當對于一個w[j,i]滿足四邊形不等式的時候，決策單調
那么我們首先來說什么叫四邊形不等式
w[i,j]+w[i+1,j+1]≤w[i+1,j]+w[i,j+1]
是不是一臉蒙蔽？
其實是網上的柿子非得撞壁，寫成這個13樣，不信你移個項
w[i+1,j+1]?w[i+1,j]≤w[i,j+1]?w[i,j]
就是這樣的，對于i+1狀態的決策集，j位置決策的增長幅度不如在i位置的決策集中j+1位置的增長幅度大
顯然這意味著，如果一個決策在i位置就已經被淘汰，無論他怎么跑，都追不上其他在i+1位置的決策了，所以有這樣的性質
對于狀態x的兩個決策位置 i≤j 如果i不如j優，則對x+1必然不選擇i
這有啥用??？就是把你原來從1枚舉變成從x?1決策點枚舉了？？
還是暴力，有個卵用？
那我們換一個角度思考，之前都是對狀態想決策，現在變成對決策想狀態。
對于一個決策j能決策的狀態區間是什么，一定是狀態集中的一段連續的區間
所以我們可以考慮這樣一個問題，（以下數字表示決策點位置編號）

對于決策1有這樣的決策區間
1111111111
對于決策2來了，他一定決策這樣的區間
1111122222
以此類推
所以我們對每個決策點決策區間維護單調棧，每來一個決策，就在單調棧中二分決策點變化位置，彈掉后面的區間，拆開當前區間即可

廢話說完了

斜率優化是個啥？？？
考慮這樣另一種形式的子類型

f[i]=mini?1j=1(a[i]?f[j]+b[i]?g[j])
美化以下柿子
f[i]=mini?1j=1(a[i]?x[j]+b[i]?y[j])
求 a?x+b?y的最值？
變成斜截式 y=?ba?x+Pb
現在一個決策點變成了一個數對， (x,y)
問題轉化成了給定一些斜率固定的直線，以及二維平面上的點集
求一條直線在平面上穿過某一點使得與y軸截距最值
直線方程？線性規劃？？
顯然是卡在凸包上的最優啊
下面分情況討論
如果 x是遞增的，斜率也是遞增的
就相當于一邊向后插點維護凸包，一邊在前面用直線卡掉不合法的點
顯然單調隊列，隊尾插點，隊頭按直線彈掉，時間復雜度O(n)。
如果x遞增，斜率不遞增，就要正常維護凸包，在凸包上二分找到直線卡的點位置。
時間復雜度 O(n?log2n)
如果x和斜率都不遞增，用平衡樹維護凸包，動態插點，刪點，反正我不會寫。
可寫的方法是cdq，對x進行cdq，左右分別維護凸包， O(n)合并凸包。
時間復雜度 O(n?log2n)

總結

以上是生活随笔為你收集整理的【斜率优化】【决策单调】xjb讲课的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。