\(\text{wqs 二分学习笔记}\)
近日屡见 wqs 二分，难以战胜，奋力研究，故有此学习笔记。
应用场景
我们常见到一类 dp：有 \(n\) 个物品，设 \(f_{i,j}\) 表示前 \(i\) 个物品，选择了 \(j\) 个物品时的代价，\(w(j,i)\) 表示选择 \(j\sim i\) 这一段物品的代价，dp 方程长成 \(f_{i,j}=\min(f_{i,k}+w(k+1,j))\) 这样的形式。那显然这样的 dp 复杂度是 \(O(n^2)\) 的，如果结合题目的特殊性质有时可以优化一些复杂度。但有些题目会加上恰好选择 \(m\) 个物品这样的限制，如果暴力在 dp 中刻画这样一个限制复杂度显然会爆炸，于是我们可以用 wqs 二分优化这样的 dp。
算法概述
我们设 \(g(x)\) 表示选择 \(x\) 个物品时的最小值，求解最大值的情况是同理的。若想要用 wqs 二分优化问题，需要题目满足这样一个性质：
- 对于每个点 \((x,g(x))\) 构成的集合是一个下凸包。
通常来讲对于 wqs 二分的题目我们难以证明这个性质，但一般地，具有这类特征的题目大多满足这个性质，如果不放心的话可以将程序与暴力 dp 对拍来验证正确性。
虽然我们无法求出每个点的坐标，但我们还是要考虑如何利用这个性质。我们用斜率为 \(k\) 的直线切这个凸包，那么当直线切到某个点时就相当于是此时的截距最小。考虑到 \(b=y-kx\)，\(y\) 的实际意义是我们求出的 dp 值，\(x\) 的实际意义是选择物品的个数，所以我们在每次 dp 转移的时候给新的 dp 值减去一个二分出来的 \(mid\)，用这个 dp 方式来转移选择物品的个数来确定此时的横坐标。那么判断求出来横坐标 \(x\) 与 \(m\) 的关系，若 \(x\le m\)，切在了左边，斜率应当变大；反之亦然。但对于下凸包，斜率 \(k\) 是负数，因此我们在写代码的时候通常将斜率按照正数来处理，将 dp 时的 \(-mid\) 变成 \(+mid\)，同时当 \(x\le m\) 时将数值变小即可。下面给出一份求最小值时的参考代码，求最大值时是类似的：
int n, m, num[N], dp[N];
pair<int, int>chk(int mid) {init();for (int i = 1; i <= n; i++)for (int j = 0; j < i; j++) {int v = dp[i], dp[j] + w(j + 1, i) + mid;if (v < dp[i]) dp[i] = v, num[i] = num[j] + 1;}return {num[n], dp[n]};
}int solve() {int l = 1, r = inf, mid = 0, ans = 0;while (l <= r) {mid = (l + r) >> 1;if (chk(mid).first <= m) ans = mid, r = mid - 1;else l = mid + 1;}return chk(ans).second - m * ans << '\n';
}
常见问题
由于经过 wqs 二分优化后的 dp 通常是一个基本的选物问题，往往有决策单调性，因此经常会和斜率优化 dp 结合起来。这就涉及到了一个易错点：共线时的取等问题。如果在二分时取较右的端点计算答案，实际意义是我们选择了较多的物品进行计算，那么我们在斜率优化 dp 判断斜率时就需要加等号来确保我们选择了更多的物品。反之我们取左端点意味着我们选择了较少的物品，那么我们就不能取等来减少物品个数。当然具体的问题还要结合实际情况来分析解决。