考虑一个问题：一个集合中有 n 个物品，每个物品有一个价值(可能为负)，请你取出 m 个物品，并且使价值之和最大。这种问题一般人选择直接排序，但是如果一个物品的价值计算方式变化了导致不能直接排序取出，甚至没有贪心策略时，应该如何做？如果直接使用二维dp还会超时有什么办法可以快速做？
推结论
实际上这个问题就是WQS问题的典型问题，我们设函数 \operatorname{g}\left(x\right) 表示取出 x 个物品时能取到的价值最大值，将每一个 \left(x,\operatorname{g}\left(x\right)\right) ，在一个平面直角坐标系上面画出来，串起来。先忽略红色直线，大概是这个样子，观察可知其凸性：
可以想到的是对于任意一个斜率为 k 的直线都能在上凸壳上找到一个点使得其直线截距最大。
假设现在已知一个斜率为 k 的直线，切到了 \left(x,\operatorname{g}\left(x\right)\right) 这个点，并且截距最大。现在已知 x (接下来默认 x 时定值，用 x 这个记号只是提醒读者有普适性)，如何求解 \operatorname{g}\left(x\right) 。
令 \operatorname{f}\left(x\right)=\operatorname{g}\left(x\right)-k\times x ，也就是每个物品价值减去 k 后能取到 x 个的最大价值。实际上 \operatorname{f}\left(x\right) 为在没有拿多少这个限制的时候，所有物品的价值减去 k 后的最优解。
证明如下：由于我们 x 是定制了，换个记号，令 \operatorname{h}\left(q\right) 表示每个物品减去 k 无限制拿 q 个的最大价值，显然 \operatorname{h}\left(q\right)=\operatorname{g}\left(q\right)-k\times q ，则有 \operatorname{h}\left(q\right)+k\times q=\operatorname{g}\left(q\right)，也就是 \operatorname{h} 表示用斜率为 k 的直线去切 \left(q,\operatorname{g}\left(q\right)\right) 的截距。用 \operatorname{h} 去考虑一个每个物品价值减 k 后的无限制的最优情况，可以分论讨论每一个 q 的取值，然后找到最小的一个 \operatorname{h} 就是无限制每个物品价值减 k 后的无限制的最优情况，但是别忘了 \operatorname{h}\left(q\right) 本质是用斜率为 k 的直线去切 \left(q,\operatorname{g}\left(q\right)\right) 的截距，显然对于这个凸包，切到 \left(x,\operatorname{g}\left(x\right)\right) 时 \operatorname{h}\left(q\right) 最大，而恰好此时 \operatorname{h}\left(x\right)=\operatorname{f}\left(x\right) 也就是 \operatorname{f}\left(x\right) 等价于每个物品价值减 k 后的无限制的最优情况。这个结论使得我们找到了一个可以快速计算的函数 \operatorname{f}\left(x\right) ，并且可以转化到 \operatorname{g}\left(x\right) 上去，从而实现快速求解。
实现
现在回到做题，我们已知了 x ，并且可以快速计算 \operatorname{f}\left(x\right) ， k 未知，目标求解 \operatorname{g}\left(x\right) 。实际上我们只需要找到这个 k 就可以了，考虑 k 单调递增变化时，在凸包上切出来的点必定按照 X 递增。那就好办了，直接二分 k 直到切到的点的 X 坐标就是 x 即可。
实际应用中，对于小数二分常常直接限定循环次数；而二分的 check() 函数就是跑一遍无限制dp只不过转移方程需要减去一个 mid (二分中的 mid ) ，然后记录转移次数，并于 x 比较，根据实际情况去二分左区间还是右区间(上凸壳/下凸壳之分)。