【学习笔记】wqs二分

Posted on 2022-02-05 Edited on 2022-04-10

在一堆好的讲解的博客中终于领悟到了原理.

在这篇学习笔记是给我这种萌新看的, 所以会写的尽可能的详细, 详细到起码我能看懂.

感谢 $Alex _ Wei$ 属实是学到了不少.

总的来讲, 算法好奇妙, 数据毒瘤就好痛苦, 要调一万年.

$wqs$ 二分优化

总结几句

常见于优化 $dp$ 中有一维是选取物品个数的 $dp$ , 常于斜率优化和二分队列搭配使用.

它比较套路, 限制选取物品个数是它明显的标志, 设 $f_i$ 表示最多, 恰好或至少选取 $i$ 个物品时的答案, 若 $f$ 这个函数有凸性, 则可以使用, 当然 $dp$ 状态并不只局限于这一种设计方式, 只要一个函数满足凸性, 就可以使用, 比赛时我们常常并不能严谨证明出函数的凸性, 大多数为感性猜测, 还有一句话, $nk$ 做不了就是凸的.

算法讲解

我们来一个例题引入, 有 $n$ 个数, 最多分成 $m$ 段, 求每段平方和的最小值.

这个是斜率优化的板子, 可以做到 $\Theta(nm)$ , 但是无论用什么其他方法, 复杂度都和 $m$ 有关, 所以考虑对 $m$ 这一维做些操作.

设 $f_{i,j}$ 表示把前 $i$ 个数分为 $j$ 段的最小代价, 把 $f_{n,i}$ 简记为 $F_i$ , 这是一个关于 $i$ 的下凸函数, 可以使用 $wqs$ 二分优化它.

所以 $wqs$ 二分究竟二分的是什么, 是斜率, 具体的, 如果用一个斜率为 $k$ 的直线去且这个凸包 $F$ , 我们会切到一个点, 不妨设为 $(x,F_x)$ , 因为 $F$ 下凸, 所以 $(x,F_x)$ 是在所有 $(i,F_i)$ 中, 用斜率为 $k$ 的直线切时与 $y$ 轴交点, 也就是截距最小的那个, 即使得 $F_x-kx$ 最小的 $x$ .

接下来, 我们使用一个非常巧妙的转化, 如何在确定 $k$ 时求出其对应的 $x$ 和 $F_x$ 这样子就能求出. 现在我们之际上是要求 $F_x-kx$ 的最小值, 这个问题可以看作, 每当多分一段, 就得将答案减去 $x$ , 求出在不限段数的情况下, 答案的最小值 $g_n$ , 以及取到的最小段数 $x$ , 而 $F_x$ 就是 $g_n+kx$ . 这个可以通过其他的 $dp$ 优化方法来实现, 这个例题中就是斜率优化, 在线性对数的时间内完成.

如果 $x=m$ , 说明已经找到了答案, 如果 $xm$ , 说明斜率不够下, 对于函数是上凸时大小关系会反转.

我们要根据 $x$ 与 $m$ 的关系调整上下界, 最终答案为 $g_n+km$ .

因为函数有凸性, 所以二分必然能找到所有可以遍历到的可能的优秀斜率, 所以算法正确性有保证.

实现细节

数据类型与时间

大部分题目 $F_i$ 是整数, 所以斜率 $\dfrac{F_{i+1}-F_i}{i+1-i}=F_{i+1}-F_i$ 也是整数, 因此 $wqs$ 二分的边界和斜率都是整数.

部分题目想涉及到小数运算, 斜率可能不是整数, 所以精度和效率很重要, 找到答案就结束二分是不错的选择, 同时也可以选择控制二分次数来达到卡时间的效果, 提前预估好精度, 只二分 $200$ 次或者其他次数可以有效减少花费时间.

三点共线

如图, 这种情况可能导致我们用原也二分不到想要的斜率, 即斜率为 $k$ 时, $x m$ .

以图为例, 不妨设 $m=x_c$ , 如果求出了 $k_2$ , 无论时切到 $B$ 点还是 $C$ 点或 $D$ 点, 求出来的斜率都相同, 所以不影响答案.

但值得注意的一点时, 二分的边界修改与 $dp$ 求出的段数最大值还是最小值息息相关.

如果在保证答案最小时, $dp$ 求出的是段数最小值, 那么 $mid$ 应该为 $\Big\lfloor\dfrac{l+r}{2}\Big\rfloor+1$ , 当 $xm$ 时应有 $r \leftarrow mid-1$ .

$k=k_3$ 时截到点 $D$ , 因为 $x_D > x_C$ , 所以 $k_3$ 一定不是我们想要的斜率, $r \leftarrow mid-1$ .

$k=k_2$ 时截到点 $B$ , 因为 $x_B < x_C$ , 所以 $k_2$ 可能是我们想要的斜率, $l \leftarrow mid$ .

如果在保证答案最小时, $dp$ 求出的是段数最大值, 那么 $mid$ 应该为 $\Big\lfloor\dfrac{l+r}{2}\Big\rfloor$ , 当 $xm$ 时应有 $r \leftarrow mid$ .

$k=k_1$ 时截到点 $B$ , 因为 $x_B < x_C$ , 所以 $k_1$ 一定不是我们想要的斜率, $l \leftarrow mid+1$ .

$k=k_2$ 时截到点 $D$ , 因为 $x_C < x_D$ , 所以 $k_2$ 可能是我们想要的斜率, $r \leftarrow mid$ .

所以, 在保证答案最优的情况下, 究竟 $dp$ 的是物品个数最大值还是最小值, 对 $wqs$ 二分的过程有很大影响.

更新答案

更新答案的时候如果是恰好, 则求出 $x$ , 及其截距 $d$ , 答案是 $d+km$ 而不是 $d+kx$ , 如果是最多则是 $d+kx$ .

如边界值变为 $mid$ , 则更新答案, 直接给答案赋值而不是取 $\min$ 或 $\max$ , 相反, 如边界变为 $mid \pm 1$ , 因为 $mid$ 处的答案并没被取到.

常用技巧

用结构体将 $dp$ 值与所选物品个数结合在一起, 不仅方便更新 $dp$ 值, 还能快速比较两个 $dp$ 值的偏序关系, 重载运算符即可, 具体实现不同题会有所不同.

struct DP {
	ll res;
	int cnt;
	DP (ll Res = 0,int Cnt = 0) {res = Res;cnt = Cnt;}
	bool operator < (const DP &rhs) const {
		return (res ^ rhs.res) ? res < rhs.res : cnt > rhs.cnt;
	}
}f[maxn][2];
DP operator + (DP x,DP y) {return DP(x.res+y.res,x.cnt+y.cnt);}