WQS 二分，也称带权二分 / DP 凸优化。

例一：分段平方和

把长度为的正整数序列分成若干段。一段的代价是和的平方加一个常数。求最小代价。

设表示个数的最小代价。

可以斜率优化。时间复杂度。

例二：分段平方和

把长度为的正整数序列分成段。一段的代价是和的平方。求最小代价。

首先我们可以设表示前个数分成段的最小价值。

算法一

可以有一个的转移

时间复杂度。

算法二：斜率优化

在算法一的基础上，由于，因此可以固定，然后使用斜率优化。时间复杂度为。

算法三：决策单调性

观察决策单调性。设，也就是的最优转移决策。

首先。因为你加入一个，只会使最后一段的价值增加。因此最后一个分割点只可能往后移。

其次。因为你多分一段，显然分割点更靠后。

因此如果我们能先计算出和，那么就有上下界了！

因此我们可以按照从小到大的顺序计算和（初始时，那么就是一个数单独一段）。因此对于相同的那些 DP 值，我们只需要考虑个决策即可。时间复杂度。

算法四：WQS 二分

我们稍微修改一下代价。我们要求，每一段有一个附带的常数代价。也就是说

那么这样计算出来，相当于代价多了。因此。

从直观的角度，越大，意味着分段的成本越高。换言之，设（也就是最小的代价对应的段数），那么当越大，就会越小。因此我们可以二分来让。这时我们可以使用例题一的算法求出。那么，也就求出了答案。

我们还可以从计算几何的角度理解这个过程。

考虑二维平面上建立个点（）。

则对应一条过原点的直线。那么，可以借此构造的个点：。

我们可以理解为是把原来的个点按照的斜率拉伸得到了的个点。

从直观的角度，越大，意味着分段的成本越高。在斜率增大的过程中，这个点中高度最低（纵坐标最小）的点的横坐标是在不断变小（单调不升）的。因此这个点构成一个下凸壳。注意，这是我们使用直观理解来感性证明的。

以某一个斜率拉伸一个凸壳，会导致它的顶点横坐标发生单调的变化。这就是为什么我们可以使用二分的方式找到顶点横坐标为的情况。那么这时把凸壳拉伸回去就可以得到的纵坐标，也就是答案。

也就是说，如果我们能快速求出凸壳顶点的纵坐标，那么我们就先想办法把我们要求的点调整为顶点，然后求出它的纵坐标，然后还原。

例题一的算法，实际上就是在求这个凸壳顶点的坐标（横坐标可以在 DP 的时候附带求出）。

这样的二分算法是王钦石（WQS）首次提出的，因此我们以 WQS 二分为之命名。

该算法的复杂度是，是值域。

例三：限权最小生成树

WQS 二分不局限于 DP 优化。考虑这个问题：

给出一张个点条边加权无向图（边权）。每条边是黑色或者白色。求白色边数恰好为的最小生成树。

设表示白色边数恰好为的 MST 边权和。

那么同样地，考虑个点。然后有一条直线。在这道题目中它表示把白边的边权额外加。那么个点被拉伸出的点就是。

从直观的角度，白边权值越大，那么 MST 中白边的数量就越少。因此随着斜率增大，凸壳的顶点会左移。因此这是一个下凸壳。

那么使用 WQS 二分即可。时间复杂度。可以使用一些简单的优化降到。

WQS 二分问题 · 一般化

大多数能够使用 WQS 二分的问题可以归为以下两类：

题型一：

给出一个长度为的正整数列，分成不超过段，一段区间的代价满足四边形不等式，求最小的代价。

注：若，均有，称满足四边形不等式（简记为“交叉小于包含”）。

题型二：

给出一个长度为的正整数列，分成不超过段，一段区间的代价满足四边形不等式，求最小的代价。

注：单元函数的四边形不等式是指，，。也就是内小于等于外。

这样的问题仍然可以使用 WQS 二分来去掉段数的限制。

注：考场上证明是凸的，建议打表。

Akvizna

你有个人。你要干掉他们。假设当前还剩下个人，则在一轮里，你可以选择个人（）干掉，得分是是，剩下个人。你需要在恰好轮里干掉所有人。求最大得分。

。

容易写出一个二维 DP。权值函数，容易证明它满足四边形不等式（实际上在本题里是反过来的。你求的是最大值，因此这里的不等式应该是的版本）。然后 WQS 二分即可。去掉的限制后，可以斜率优化 DP。

时间复杂度。精度开能过。

代码

林克卡特树

给出一棵边带权的树，要求删除其中恰好条边，再加入条权边使得仍是一棵树，最大化新树的直径。

可能有负权边。

。

题意转化：将原树分成个连通块，最大化每个连通块直径的和。

我们将一个点当作退化的路径。那么进一步转化为，求原树上互不（点）相交的条链的权值和的最大值。

考虑树形 DP，设表示的子树内有条链，的度数是（）的权值和的最大值。的度数是指，它是否作为链的端点、中间点或者不在链上。

转移是背包合并。

对于原树，设表示互不相交的条链的权值和的最大值。仍然给他加一条直线。那么直觉告诉我们越大，最优的越大（顶点随斜率的增大右移）。因此它是个上凸壳。打表也可以验证。

因此二分求出最优的即可。也就是说，一条链的额外代价是，在不限制链数的情况下，最大化总的权值和。则把原 DP 的第二维去掉即可。

时间复杂度。

代码

参考文献

王钦石，浅析一类二分方法，IOI2012 中国国家集训队第二次作业自选部分。