动态规划——带权二分优化DP 学习笔记

动态规划——带权二分优化DP 学习笔记

引入

带权二分其实并不一定用于优化 DP,也可能用于优化贪心等最优化的算法。

带权二分也叫 WQS 二分,最初由王钦石在他的 2012 年国家集训队论文中提出。

定义

使用情况

  • 要解决一个最优化问题(求最大 / 最小值)
  • 有一个限制,一般是某个参数要求一定恰好为 \(k\)

而带权二分就可以很好的解决[恰好 \(k\)]的限制;以选物品取最大收益为例:

  • \(f(k)\) 为恰好选 \(k\) 个时的最大收益,将所有的 \((k, f(k))\) 画出来,图像必须组成一个凸包。
  • 因此就可以打表看,是否组成了一个凸包,如果是,则可以考虑带权二分优化。

使用方法

例:求 \(f(k)\) 的值,我们不会求 \(f(k)\) 或者其复杂度不可接受,但是我们可以求出所有 \(1\sim n\) 中的最优解 \(f(t)\) 及对应的 \(t\),因此我们就可以通过一些处理,将 \(f(k)\) 变为最小值,即将全局最优解变为 \(k\)

什么方法?我们设一个额外的 \(w\),每次选一次物品以后就将结果加上 \(w\),也就是,我们设一个新的转移方程 \(g_k=f_k+kw\)

注意:严谨的,是『选一次』,不是『选一个』。因为有的题目选一次对应一段区间,即多个物品。

可以预见到的,原函数(左)会变为(右):

要注意的是,\(w\) 也可能为负;因此总会有一个 \(w\) 使得全局最优解为 \(g(k)\),如下:

  • 可以想见,如果 \(w\) 继续增大,那么最小值点 \(x_0\) 会继续变小;
  • 如果 \(w\) 减小以至于变成负数,那么最小值点 \(x_0\) 会不断变大;

那么总会有一个 \(w\),使得最小值在 \(k\) 处取到,那不就可以二分了嘛。

我们二分一个值 \(w\)(边界可以设置地大一些,当然也可能得根据题目的数据范围调一调),现在问题转化为,求 \(g(x)\) 的最小值点 \(x_0\)

此时,不管用 DP 还是贪心啥的方法,求出 \(g(x)\) 的最小值 \(g(x_0)\),顺便求出此时的最小值点 \(x_0\)

  • \(x_0<k\),那就让 \(w\) 变小点;
  • \(x_0>k\),那就让 \(w\) 变大点。

最终,我们就能让 \(x_0=k\),也就是当全局最优解取到 \(g(k)\) 的时候,我们是不是就成功的求出了原问题 \(f(k) = g(k) - kw\) 呢?

警惕

既然是二分,就一定要仔细考虑 \(l,r,mid\) 的取值以及更新边界的条件,总之,注意代码细节!

应用

例题讲解

题目:P2619 Tree I

  • 画出函数来:

  • 凸函数好吧,所以给白边加一个 \(w\) 的额外权:
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;
}
  • 此题完结。

题单

见:https://www.luogu.com.cn/training/393257

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

热门相关:白首妖师   重生成偏执霍少的小仙女   让女员工轮流吃   上将大叔,狼来了!   悠哉兽世:种种田,生生崽