WQS二分解题流程分析

· · 算法·理论

WQS 二分解题流程分析

1. 引入

例题：P1792 [国家集训队] 种树

题目分析

给定一个长度为 n 的环，相邻两个位置不可同时选择，每个位置若被选择，则对答案贡献为 a_i。求最大可能贡献。

状态表示
设 dp[i][j] 表示前 i 个位置选取了 j 个时的最大贡献，则有：

dp[i][j] = \max_{k=1}^{i-2} \{ dp[k][j-1] + \operatorname{cost}(k, i) \}

显然此方式的时间复杂度为 O(n^2m)，严重超时。对状态转移进行优化，得：

dp[i][j] = \max \begin{cases} dp[i-1][j],\quad \text{不选第 $i$ 个数} \\ dp[i-2][j-1] + a_i,\quad \text{选第 $i$ 个数} \end{cases}

此时时间复杂度为 O(nm)，仍然会超时。因此考虑进一步优化。

斜率单调性分析
设 g(x) 表示选取 x 个位置时的最大贡献，若 g(i) 满足以下关系就可以考虑使用 WQS 二分：

g(i+1) - g(i) \le g(i) - g(i-1)

贪心考虑，每次选取贡献尽可能大的加入答案，因此越到后面，增加量越少。

若 g(i-1) = w，则 g(i) = w + a_j, g(i+1) = w + a_j + a_k，左边为 a_k，右边为 a_j。根据贪心分析，有 a_k \le a_j，因此可以使用 WQS 二分进行优化。

DP 构建与求解
由以上分析，本题的 g(x) 形成的图像为一个上凸包（斜率单调递减），因此对斜率进行二分。斜率 k 随着 x 的增大而减小。判断直线与凸包的交点是否大于 m，若小于 m，则调大斜率。至于找到切点，由于过切点的直线一定是同一斜率下截距最大的，可以通过此规律找到。

设 f(x) = g(x) - kx,\ k \in [0, 1]，表示截距的集合，同时也表示选取 x 个数，每个数的贡献减去 k 的答案。因此，使用 DP 求出 f(x) 的答案作为二分判断条件，然后使用 WQS 二分求解答案，最终答案为 ans = f + l \times k。

2. 流程总结

  1. 判断是否可以使用 WQS 二分

    先列出 WQS 二分的条件：

    g(i+1) - g(i) \le g(i) - g(i-1)

    然后贪心地考虑，判断是否满足该式（可参考例题推导）。若满足，则可以使用且构成上凸包；若为“大于等于”，同样可以使用且构成下凸包。

  2. 构建 DP

    由上述分析得知凸包类型后，观察斜率（切点）的调整与目标的关系。若为上凸包，则看直线与凸包的交点是否大于目标，若小于目标，则调大斜率；若为下凸包，则反向调整。

    寻找切点时，过切点的直线一定是同一斜率下截距最大的，可以设 f(x) 表示截距的集合，有 f(x) = g(x) - kx,\ k \in [0, 1]，建立截距与答案的关系（一般处理方式如例题）。使用 DP 求解 f(x)，同时记录切点的横坐标。用二分法寻找答案即可。