浅谈 Wqs 二分

主要是今天写 「九省联考 2018」林克卡特树 的时候遇到了，就学一下。

使用条件

  • 题目中对于一种 $\tt Dp$ 有限制，但是如果没有限制，其复杂度是正确而且很好求的。举个例子来说：

将一棵树划分成 $k$ 条链，我们 $\tt Dp$ 的时候只需要记录当前节点是否被匹配过，以及是否正在被匹配即可，而且我们还要考虑总共有几条链，进行划分。但是如果不考虑链的数量，这个 $\tt Dp$ 显然是 $O(n)$ 的。

对于背包类型的 $\tt Dp$ 来说如果有物品数量的限制，之前常常会有 $O(n^2)$ 不得不枚举的复杂度，我们将其消去常常就可以得到正确的复杂度。

  • 对于限制的依赖，可以考虑限制是 $x$，贡献是 $f(x)$，对于点对 $(x, f(x))$ 其构成一个凸包。

具体实现

对于一个凸包考虑枚举斜率进行切割，对于一个上凸包来说斜率是从左到右逐渐递减的。

我们考虑枚举一个斜率 $k$，那么我们的截距是什么呢，显然就是 $f(x) - kx$。

显然对于所有的 $g(x) = f(x) - kx, (x, g(x))$ 同样构成相同的凸包。

那么我们可以考虑二分一个 $k$，计算最优秀的 $x, g(x)$。

如果说 $x < m$，其中 $m$ 是题目中的限制，那么我们肯定是要将斜率减小，否则是增大。

边界处理

考虑相同的一段是怎么处理的，我们可以考虑对于相同的一段我们钦定保留 $x$ 最小的。

每次二分的时候，当 $k < m$ 的时候，让 ans = mid, R = mid - 1即可。

1
2
3
4
5
6
7
while(L <= R) {
    mid = (L + R) >> 1;
    dfs(1, 0);
    if(f[1][0].y == K) return printf("%lld\n", f[1][0].x + mid * K), 0;
    if(f[1][0].y < K) R = mid - 1, ans = mid;
    else L = mid + 1;
}