搜 索

WQS二分/带权二分

  • 454阅读
  • 2021年12月21日
  • 0评论
首页 / 学习笔记 / 正文

WQS 二分 / 带权二分

首先,我们得了解 wqs 二分是用来干嘛的

求出有限制地恰好选 $k$ 个的最优答案。如把一个序列恰好分成 $\text{k}$ 段,最小化平方和

这类问题用 $\text{wqs}$ 二分有一个前提,设 $f(k)$ 为恰好选 $k$ 个的答案,则 $f(k)$ 关于 $k$ 的图像一定得是一个 凸函数 (即斜率单调)。

并且我们要能快速地求出最优值。

这样的话每一个点就会有一个切线,并且 切线斜率单调 。我们只要二分切线的斜率,找他在凸包上最优的切点,然后得到相应的横坐标。

但是枚举了斜率怎么找最优的点呢?

由图可知,过最优点的直线与 $\text{y}$ 轴的 截距 最大。假设截距的函数为 $g(x)$ ,表示过 ${(x , f(x) )}$ 的直线与 $\text{y}$ 轴的截距。那么 $g(x)=f(x)-kx$ 。

我们可以把所有的物品价值都减去 $k$ ,这样新的 $f'(x)=f(x)-kx=g(x)$ 。于是我们可以快速得到最优的值以及 $x$ 。剩下的就交给二分就好了。

但是注意,如果存在有 三点共线 的情况,为了避免麻烦,我们强制切 最左端点 ,这样我们可以通过左端点和斜率来算出中间的点了,即 $f(x)=g(x)+kx$ 。当然你想切最右端点也可以。

并且我们有时候枚举的 $k$ 可以只是 整数 。为什么呢?考虑相邻两个点 $(x,f(x))$ 和 $(x+1,f(x+1))$ ,肯定存在斜率为 $f(x+1)-f(x)$ 的直线可以同时切到两点。只要 $f(x)$ 为整数,我们就不用二分实数。

关于方案输出

如果不存在三点共线的话,肯定直接就能求出方案啥的。否则我们可以通过强制选一个东西,对剩下的进行 wqs 二分,看是否是最优解,然后递归操作即可。

DP
评论区
暂无评论
avatar