# 问题引入

如果你遇到了一类这样的问题：

有 $n$ 个物品，你必须在遵守一定限制的前提下从中选出 $m$ 个物品，最大 / 小化这 $m$ 个物品的总价值。

你可能会想到动态规划，但是这样动态规划时间复杂度是 $O(nm)$ 起步的。

但如果这个问题去掉 $m$ 个物品的要求，你可以直接用一维动态规划，或许会更容易解决；而且你发现，如果要求选 $x$ 个物品的情况下最大 / 小价值为 $g(x)$，函数 $g(x)$ 具有上凸 / 下凸的性质（实际上大多数这类问题都有这个性质），那么你可以用到一个利器来优化朴素的二维 $\text {dp}$：$\text {wqs}$ 二分。

# 算法介绍

我们设 $k$ 表示要求选的物品个数，$g(k)$ 表示选出 $k$ 个物品所能得到的最大 / 小价值，以 $k$ 为横轴，以 $g(k)$ 为纵轴，可以画出这样的图：

凸包有什么性质？斜率单调递减！如果我们考虑用一条直线去切这个凸包：

我们总能切到一个最高点，设这个点是 $(x, g(x))$，直线斜率为 $c$，那么有如下等式成立：

$$g(x) = cx + b$$

即：

$$b = g(x) - cx$$

那么 $-cx$ 有什么实际含义吗？我们可以理解为 把每个物品的价值都减去一个 $c$，则我们选出的 $x$ 个物品总价值就正好减去了 $cx$！

如果我们一开始设定了这条直线的斜率为 $c$，然后我们把每个物品的价值都减去 $c$，进行一次不限定物品个数的一维 $\text {dp}$，能找到一个最大值，这个最大值就对应着这条相切直线的截距，如果我们在 $\text {dp}$ 的过程中还记录下我们选了多少个物品，就能很容易地反推出 $g(x)$ 是多少！

于是我们的优化思路就出来了：我们二分这条直线的斜率，找到一个斜率使直线能和我们需要的 $(k, g(k))$ 相切，我们就能反推出 $g(x)$ 是多少！

关于斜率的上下界，我们找到 $(0, g(0)), (1, g(1))$ 之间的斜率和 $(n - 1, g(n - 1)), (n, g(n))$ 之间的斜率就可以确定下来。

大体思路就是这样，时间复杂度为 $O(n \log p)$，其中 $n$ 为物品个数（此处我们假定一维 $\text {dp}$ 是线性可做的），$p$ 是价值的值域。但我们还有一个细节问题需要说明。如果我们的图长这样：

也就是说存在一条直线和图像的多个点相切的话，我们该如何判断当前斜率是大了还是小了？我们不妨把切到的这个 $x$ 永远设定为最小的那个 $x$，我们在二分的过程中就能处理这个问题了。

由此可见，$\text {wqs}$ 二分使用的关键在于证明答案的凹凸性。一般的证明思路是 $g(k) - g(k - 1) > g(k + 1) - g(k)$ 或 $g(k) - g(k - 1) < g(k + 1) - g(k)$，即后面越选物品能获得的价值越大 / 小。

废话不多说，上例题！

# 例题

# 例题 1. 朝日捡石头

C6 - 2024级程序设计基础第六次上机赛 J. 朝日捡石头

这是一道 $\text {wqs}$ 二分的模板题。