这是本文档旧的修订版！

WQS二分

wqs二分可以解决形如在$n$个物品中选$k$个物品最大化/最小化总价值。直接dp一般是$O(nk)$的，而如果题目满足下面的条件，就可以用wqs二分做到$O(n \log n)$。
以最大化价值为例，设$x$表示选择物品的个数，设$f(x)$表示选$x$个物品的最大值，如果$f(x)$关于$x$是凸函数或凹函数，那么图象就是一个凸包。虽然我们不知道具体凸包长什么样，但是我们可以利用凸包的性质，通过二分直线的斜率使得这条直线与$(k,f(k))$这个点相切，从而间接得到$f(k)$的值。

CF739E