動態(tài)規(guī)劃——帶權(quán)二分優(yōu)化DP 學(xué)習(xí)筆記
引入
帶權(quán)二分其實(shí)并不一定用于優(yōu)化 DP，也可能用于優(yōu)化貪心等最優(yōu)化的算法。
帶權(quán)二分也叫 WQS 二分，最初由王欽石在他的 2012 年國家集訓(xùn)隊(duì)論文中提出。
定義
使用情況
- 要解決一個最優(yōu)化問題（求最大 / 最小值）
- 有一個限制，一般是某個參數(shù)要求一定恰好為 \(k\)
而帶權(quán)二分就可以很好的解決［恰好 \(k\) 個］的限制；以選物品取最大收益為例：
- 設(shè) \(f(k)\) 為恰好選 \(k\) 個時的最大收益，將所有的 \((k, f(k))\) 畫出來，圖像必須組成一個凸包。
- 因此就可以打表看，是否組成了一個凸包，如果是，則可以考慮帶權(quán)二分優(yōu)化。
使用方法
例：求 \(f(k)\) 的值，我們不會求 \(f(k)\) 或者其復(fù)雜度不可接受，但是我們可以求出所有 \(1\sim n\) 中的最優(yōu)解 \(f(t)\) 及對應(yīng)的 \(t\)，因此我們就可以通過一些處理，將 \(f(k)\) 變?yōu)樽钚≈?，即將全局最?yōu)解變?yōu)?\(k\)。
什么方法？我們設(shè)一個額外的 \(w\)，每次選一次物品以后就將結(jié)果加上 \(w\)，也就是，我們設(shè)一個新的轉(zhuǎn)移方程 \(g_k=f_k+kw\)。
注意：嚴(yán)謹(jǐn)?shù)?，是『選一次』，不是『選一個』。因?yàn)橛械念}目選一次對應(yīng)一段區(qū)間，即多個物品。
可以預(yù)見到的，原函數(shù)（左）會變?yōu)椋ㄓ遥?/p>
要注意的是，\(w\) 也可能為負(fù)；因此總會有一個 \(w\) 使得全局最優(yōu)解為 \(g(k)\)，如下：
- 可以想見，如果 \(w\) 繼續(xù)增大，那么最小值點(diǎn) \(x_0\) 會繼續(xù)變?。?/li>
- 如果 \(w\) 減小以至于變成負(fù)數(shù)，那么最小值點(diǎn) \(x_0\) 會不斷變大；
那么總會有一個 \(w\)，使得最小值在 \(k\) 處取到，那不就可以二分了嘛。
我們二分一個值 \(w\)（邊界可以設(shè)置地大一些，當(dāng)然也可能得根據(jù)題目的數(shù)據(jù)范圍調(diào)一調(diào)），現(xiàn)在問題轉(zhuǎn)化為，求 \(g(x)\) 的最小值點(diǎn) \(x_0\)。
此時，不管用 DP 還是貪心啥的方法，求出 \(g(x)\) 的最小值 \(g(x_0)\)，順便求出此時的最小值點(diǎn) \(x_0\)。
- \(x_0<k\)，那就讓 \(w\) 變小點(diǎn)；
- \(x_0>k\)，那就讓 \(w\) 變大點(diǎn)。
最終，我們就能讓 \(x_0=k\)，也就是當(dāng)全局最優(yōu)解取到 \(g(k)\) 的時候，我們是不是就成功的求出了原問題 \(f(k) = g(k) - kw\) 呢？
警惕
既然是二分，就一定要仔細(xì)考慮 \(l,r,mid\) 的取值以及更新邊界的條件，總之，注意代碼細(xì)節(jié)！
應(yīng)用
例題講解
題目：P2619 Tree I
- 畫出函數(shù)來：
- 凸函數(shù)好吧，所以給白邊加一個 \(w\) 的額外權(quán)：
int l = -110, r = 110;
while (l <= r) {
int mid = l + r >> 1; Kruskal(mid);
if (now0 >= k) {
ans = ansg - k * mid;
r = mid + 1;
} else r = mid - 1;
}
- 此題完結(jié)。
題單
見：https://www.luogu.com.cn/training/393257文章來源：http://www.zghlxwxcb.cn/news/detail-711667.html
Reference
[1] https://www.mina.moe/archives/6349
[2] https://www.cnblogs.com/Dfkuaid-210/p/wqs_bisect.html
[3] https://blog.csdn.net/Emm_Titan/article/details/124035796
[4] https://blog.csdn.net/weixin_45429627/article/details/109270538
[5] https://blog.csdn.net/Huah_2018/article/details/113796445文章來源地址http://www.zghlxwxcb.cn/news/detail-711667.html
到了這里，關(guān)于動態(tài)規(guī)劃——帶權(quán)二分優(yōu)化DP 學(xué)習(xí)筆記的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
