WQS 二分

引入

本文介绍利用 WQS 二分优化动态规划问题的方法。在不同的文章中，它也常称作带权二分、凸优化 DP、凸完全单调性 DP、Lagrange 乘子法等，在国外也称作 Aliens Trick。它最早由王钦石在《浅析一类二分方法》一文中总结。

WQS 二分通常用于解决这样一类优化问题：它们带有数量限制，直接求解代价较高；但一旦去除这一限制，问题本身就变得容易得多。

比如，假设要解决的问题是，要从 $n$ 个物品中选取 $m$ 个，并最优化某个较复杂的目标函数。如果设从前 $i$ 个物品中选取 $j$ 个，目标函数的最优值为 $f(i,j)$，那么原问题的答案就是 $f(n,m)$。这类问题中，状态转移方程通常是二维的。直接实现该状态转移方程，时间复杂度是 $O(nm)$ 的，难以接受。

进一步假设，没有数量限制的最优化问题容易解决。但是，选取到的最优数量未必满足原问题的数量限制。假设选取的物品过多。那么，就可以考虑在选取物品时，为每个选取到的物品都附加一个固定大小的惩罚 $k$（即「带权二分」中的「权」），仍然解没有数量限制的最优化问题。根据 $k$ 的取值不同，选取到的最优数量也会有所不同；而且，随着 $k$ 的变化，选取到的最优数量也是单调变化的。所以，可以通过二分，找到 $k$ 使得选取到的最优数量恰为 $m$。假设此时目标函数的最优值为 $f_k(n)$，那么，只要消除额外附加的惩罚造成的价值损失，就能得到原问题的答案 $f(n,m)=f_k(n)+km$。假设单次求解附加惩罚的问题的复杂度是 $O(T(n))$ 的，那么，算法的整体复杂度也就降低到了 $O(T(n)\log L)$，其中，$O(\log L)$ 是二分 $k$ 需要的次数。

这就是 WQS 二分的基本想法。但是，这一想法能够行得通，前提是 $f(n,m)$ 关于 $m$ 是凸的。否则，可能不存在使得最优数量恰为 $m$ 的附加惩罚 $k$。这也是这种 DP 优化方法常常称为「凸优化 DP」或「凸完全单调性 DP」的原因。

传统方法

设非空集合 $X$ 为（有限的）决策空间，$f:X\to \mathbf{R}$ 为目标函数，且另有函数 $g:X\to {\mathbf{R}}^d$ 用于施加限制。需要求解的问题，可以看作是计算如下最优化问题的价值函数 $v(y)$ 在某处的取值：

$$\begin{array}{rl}v(y)=\underset{x\in X}{min}& f(x)\\ \text{subject to }& g(x)=y.\end{array}$$

比如，对于前文提到的限制数量的问题，$X$ 可以理解为所有物品集合的子集族，$x\in X$ 是单个子集，$f(x)$ 是单个子集的价值函数，$g(x)$ 是子集 $x$ 中的元素个数。当然，$g(x)$ 并非只能是数量限制，后文提供了更为广泛的限制条件的例子。

几何直观

因为算法竞赛中遇到的大多数问题都是组合优化问题，决策空间 $X$ 通常没有良好的结构，所以，可以转而考察集合

$$\mathcal{D}=\{(g(x),f(x))\in \mathbf{R}\times {\mathbf{R}}^d:x\in X\}.$$

传统方法能够解决的主要是 $d=1$ 的情形，即只有一个限制的情形。下图提供了此时点集 $\mathcal{D}$ 的一种可能的图示。

图中的红点和蓝点是 $X$ 中所有可能的选择投影在平面 $(g(x),f(x))$ 上得到的集合 $\mathcal{D}$。于是，原问题所要求的就是横坐标为 $y$ 的那些点中，纵坐标的最小值 $v(y)$。当 $y$ 变动时，所有这样的点 $(y,v(y))$ 就构成了图中的红点的集合。

为了求得点 $(y,v(y))$ 的纵坐标，可以考虑用斜率为 $\lambda \in \mathbf{R}$ 的直线去切集合 $\mathcal{D}$。如图所示，当直线的斜率选取得恰当时，经过点 $(y,v(y))$ 的那条直线，是所有经过集合 $\mathcal{D}$ 中的点且斜率为 $\lambda$ 的直线中，截距 $f(x)-\lambda g(x)$ 最小的。将这一最小值记为

$$h(\lambda )=\underset{x\in X}{min}f(x)-\lambda g(x).$$

那么，因为 $(y,v(y))$ 同样位于该直线上，就可以得到原问题的解

$$v(y)=h(\lambda )+\lambda y.$$

假设对于所有合理范围的 $\lambda$，上述函数 $h(\lambda )$ 都是容易求解的。这在算法竞赛中常常是成立的，因为它去掉了原问题中的限制条件。那么，现在面临的最为重要的两个问题，就是

1. 是否存在这样的直线斜率 $\lambda$，使得它的截距最小值恰好取得在点 $(y,v(y))$ 处，以及
2. 如果存在，如何找到这样的斜率 $\lambda$。

第一个问题相对容易解决。因为当直线斜率 $\lambda$ 发生变化时，所有这些直线切出的集合（即它们对应的上半平面的交）必然是一个凸集。因此，这些直线能够经过某个点，当且仅当这个点在该凸集的下凸壳上。这等价于说，函数 $v(y)$ 是 凸函数。

第二个问题则更为精细。因为所求点的横坐标已经知道是 $y$，所以，一个自然的思路是，计算 $h(\lambda )$ 时，顺便求出限制函数 $g(x)$ 在当前最优解 $x_{\lambda }$ 处的取值。比如，在前文提到的例子中，求解带惩罚的问题时，可以记录带惩罚的目标函数取得最优解时，选取的物品数量。然后，将 $g(x_{\lambda })$ 与所期望的 $y$ 进行比较，并相应调整下次计算时的 $\lambda$ 的取值。这就是最为传统的 WQS 二分的方法。

总结一下，传统 WQS 二分的基本流程如下：

1. 初始时，选取一个 $\lambda$ 的合理的区间；
2. 在当前的区间中选择一个 $\lambda$；
3. 求解带惩罚的问题 $h(\lambda )=\underset{x\in X}{min}f(x)-\lambda g(x)$，并记录它的最优解 $x_{\lambda }$ 处 $g(x)$ 的取值 $g(x_{\lambda })$；
4. 如果 $g(x_{\lambda })=y$，就得到原问题的最优价值 $v(y)=h(\lambda )+\lambda y$，直接结束算法；
5. 否则，根据 $g(x_{\lambda })$ 与 $y$ 的大小关系，调整 $\lambda$ 的区间，并回到步骤 2。

这一基本流程已经足以解决一些问题，但并不完善。接下来，本文将讨论对这一基本流程的改进。

共线情形的处理

在应用基本流程时，首先遇到的问题就是共线情形无法正确处理。

如果点集 $\mathcal{D}$ 的下凸壳上有三个及以上的红点共线，那么在上述基本流程中，可能无法正确地判断 $g(x_{\lambda })$ 与 $y$ 的大小关系。比如，设共线的三个红点的横坐标分别为 $y_1,y_2,y_3$，且它们共线的直线的斜率为 ${\lambda }^{\ast }$。那么，要正确求解 $v(y_2)$，就必须保证算法终止时，最后计算的问题是 $h({\lambda }^{\ast })$，因为 ${\lambda }^{\ast }$ 是唯一一个最小化截距时能够经过点 $(y_2,v(y_2))$ 的直线的斜率。但是，因为在求解 $h({\lambda }^{\ast })$ 的过程中，记录的 $g(x_{{\lambda }^{\ast }})$ 可能是 $y_1,y_2,y_3$ 中的任意一个。如果记录到的 $g(x_{{\lambda }^{\ast }})$ 不等于 $y_2$，那么算法将错误地继续运行，并向着背离 $y_2$ 的方向调整 $\lambda$ 的区间，最终将得到错误的结果。

为了解决共线的情形，一种处理方法是在记录最优解 $x_{\lambda }$ 对应的 $g(x_{\lambda })$ 时，总是使之尽可能大（或尽可能小）。同时，将二分中的终止条件从寻找恰好满足 $g(x_{\lambda })=y$ 的 $\lambda$ 改为寻找满足 $g(x_{\lambda })\ge y$（或 $g(x_{\lambda })\le y$）的最小（或最大）的 $\lambda$。在上一段的例子中，这相当于计算问题 $h({\lambda }^{\ast })$ 时，输出的 $g(x_{{\lambda }^{\ast }})$ 是 $y_3$。这就保证了算法终止时，最后计算的问题是 $h({\lambda }^{\ast })$。实现这一方法时，需要注意最后输出的不是 $h(\lambda )+\lambda g(x_{\lambda })$ 而是 $h(\lambda )+\lambda y$，因为记录的 $g(x_{\lambda })$ 未必等于实际的限制 $y$。

另一种处理方法是实数二分。如果问题涉及的数字都是整数，显然，WQS 二分中的斜率也是整数。在二分中引入实数，是为了保证错误地排除正确选项 ${\lambda }^{\ast }$ 时，可以通过小数部分调整回来，最终逼近正确答案 ${\lambda }^{\ast }$。例如，在上面的例子中，如果计算问题 $h({\lambda }^{\ast })$ 时，记录的 $g(x_{{\lambda }^{\ast }})$ 是 $y_1$，小于所希望的 $y_2$，那么，算法就会转而考虑区间 $({\lambda }^{\ast },{\lambda }_r]$，其中，${\lambda }_r$ 是 $\lambda$ 所在区间的右端点。对于整数的情形，这一区间实际应该写作 $[{\lambda }_{\ast }+1,{\lambda }_r]$，这就排除了在后续算法中接近正确答案 ${\lambda }^{\ast }$ 的可能。但是，实数二分时，考虑的区间仍然是 $({\lambda }^{\ast },{\lambda }_r]$，而且，对于该区间中的 $\lambda$，求解 $h(\lambda )$ 时记录的 $g(x_{\lambda })$ 总是不小于 $y_3$，从而严格大于 $y_2$ 的。因此，随着算法继续进行，会不断地舍去右半区间，从而，最终得到的 $\lambda$ 的范围可以保证在 ${\lambda }^{\ast }$ 附近。当然，因为已经知道所求的斜率是一个整数，实数二分终止时的精度不必太高，只要能保证二分的区间中只包含一个整数即可，这一整数就是要寻找的 ${\lambda }^{\ast }$。

正确地处理共线情形后，WQS 二分足以解决绝大多数算法竞赛会遇到的 WQS 二分的问题。但是，这一方法仍然存在一些不足之处：它无法处理 $g(x_{\lambda })$ 难以记录的情形，也无法处理高维 WQS 二分中多个点共面的情形。本文将进一步考察最优化问题 $v(y)$ 的性质，并提出更为一般的处理方法。

对偶方法

本节介绍一种 WQS 二分的实现方法，它只要求对于所有 $\lambda \in {\mathbf{R}}^d$，可以高效地计算

$$h(\lambda )=\underset{x\in X}{min}f(x)-\lambda \cdot g(x)$$

的取值，且原问题的最优价值 $v(y)$ 是关于 $y\in {\mathbf{R}}^d$ 的凸函数¹。用一句话概括，本节将证明原问题的价值函数 $v(y)$ 就等于它的对偶问题的最优价值

$$v^{\star }(y)=\underset{\lambda \in {\mathbf{R}}^d}{sup}h(\lambda )+\lambda \cdot y,$$

而对偶问题的目标函数是关于 $\lambda \in {\mathbf{R}}^d$ 的凹函数，从而是单峰函数，可以通过 三分法 或 黄金分割法 高效地求解，复杂度仍然是 $O(T(n){\log }^{d}L)$ 的。这就完全地解决了传统 WQS 二分方法中记录 $g(x_{\lambda })$ 的值可能会出现的问题，同时，允许将 WQS 二分的思想应用至高维的情形。

另外，本节还说明，$g(x_{\lambda })$ 的范围可以通过 $h(\lambda )$ 求得，而无需在求解 $h(\lambda )$ 时额外记录。例如，对于 $d=1$ 且问题只涉及整数的情形，可以证明 $g(x_{\lambda })$ 的取值范围恰为

$$[h(\lambda -1)-h(\lambda ),h(\lambda )-h(\lambda +1)].$$

这实际上也对于不得不采取前文所述二分流程的题目，提供了又一种解决共线问题的方法。

接下来，本节将用凸分析的理论证明这些结论成立。至于这些方法的具体应用，可以参考 例题 一节。

Lagrange 对偶

考虑用 Lagrange 乘子法 解决该问题。引入 Lagrange 乘子 $\lambda \in {\mathbf{R}}^d$，那么，Lagrangian 可以写作

$$L(x,\lambda ,y)=f(x)-\lambda \cdot g(x)+\lambda \cdot y.$$

因为只要 $g(x)-y$ 有一个分量非零，就可以让相应的 $\lambda$ 的分量趋于（正或负）无穷，所以有

$$\underset{\lambda \in {\mathbf{R}}^d}{sup}L(x,\lambda ,y)=\{\begin{array}{ll}f(x),& g(x)=y,\\ +\mathrm{\infty },& \text{otherwise}.\end{array}$$

这说明，原问题可以写作

$$\begin{array}{rl}v(y)& =\underset{x\in X}{min}\underset{\lambda \in {\mathbf{R}}^d}{sup}L(x,\lambda ,y).\end{array}$$

交换两次最值操作，就得到它的 对偶问题：

$$\begin{array}{rl}{v}^{\star }(y)& =\underset{\lambda \in {\mathbf{R}}^d}{sup}\underset{x\in X}{min}L(x,\lambda ,y)\\ & =\underset{\lambda \in {\mathbf{R}}^d}{sup}h(\lambda )+\lambda \cdot y.\end{array}$$

马上要说明的是，在 $v(y)$ 是关于 $y$ 的凸函数的条件下，强对偶（strong duality）成立，即 $v^{\star }(y)=v(y)$。

凸共轭

为了说明强对偶成立，需要引入凸共轭的概念。

凸共轭

对于函数 $f:{\mathbf{R}}^d\to \mathbf{R}\cup \{\pm \mathrm{\infty }\}$，它的 凸共轭（convex conjugate），或称 Legendre–Fenchel 变换（Legendre–Fenchel transformation），是指函数

$$f^{\ast }(x^{\ast })=\underset{x\in {\mathbf{R}}^d}{sup}{x}^{\ast }\cdot x-f(x).$$

从变量 $x^{\ast }$ 的角度看，$f^{\ast }(x^{\ast })$ 是一系列线性函数的上确界，所以，必然是 ${\mathbf{R}}^d$ 上的凸函数。

超平面的「斜率向量」和「截距」

本文所讨论的向量空间 ${\mathbf{R}}^{d+1}$ 中的超平面的方程都具有形式

$$y=k\cdot x+b.$$

也就是说，本文不会涉及平行于 $y$ 轴的超平面。为表述方便，本文并不严谨地将 $k$ 称为该超平面的「斜率向量」，$b$ 称为该超平面的「截距」。将这一超平面的方程写成更标准的形式，就是

$$k\cdot x-y=-b.$$

它的一个法向量是 $(k,-1)$。因此，所谓的斜率向量其实是将超平面的法向量归一化使得它的最后一个分量等于 $-1$ 时，所得到的法向量的前 $d$ 个分量。

几何直观上，函数 $f(x)$ 的凸共轭描述的是，对于所有斜率向量为 $x^{\ast }$ 且与函数 $f(x)$ 的上境图

$$\mathrm{epi}f=\{(x,y)\in {\mathbf{R}}^d\times \mathbf{R}:f(x)\le y\}$$

相交的超平面，截距 $f(x)-x^{\ast }\cdot x$ 的最小值就是 $-f^{\ast }(x^{\ast })$。换句话说，函数 $f(x)$ 总在超平面 $y=x^{\ast }\cdot x-f^{\ast }(x^{\ast })$ 上方，且与该平面切于点 $(x_0,f(x_0))$；当然，可能存在其余的切点。这样的超平面，称为 $f(x)$ 在 $x_0$ 处的 支撑超平面（supporting hyperplane）。函数 $f(x)$ 的一个支撑超平面的截距由它的斜率向量唯一确定，凸共轭就提供了这个从斜率向量到截距的映射。

在集合 $X$ 上最小化 $f(x)-\lambda \cdot g(x)$ 就等价于在集合 $\{(y,v(y))\}$ 上最小化 $v(y)-\lambda \cdot y$：

$$\begin{array}{rl}\underset{x}{min}f(x)-\lambda \cdot g(x)& =\underset{y\in g(X)}{min}(\underset{x\in X:g(x)=y}{min}f(x)-\lambda \cdot g(x))\\ & =\underset{y\in g(X)}{min}(\underset{x\in X:g(x)=y}{min}f(x))-\lambda \cdot y\\ & =\underset{y\in g(X)}{min}v(y)-\lambda \cdot y.\end{array}$$

因此，有

$$h(\lambda )=\underset{y\in g(X)}{min}v(y)-\lambda \cdot y=-v^{\ast }(\lambda ).$$

这说明 $h(\lambda )$ 是关于 $\lambda \in {\mathbf{R}}^d$ 的凹函数。进而，有

$$v^{\star }(y)=\underset{\lambda \in {\mathbf{R}}^d}{sup}\lambda \cdot y-v^{\ast }(\lambda )=v^{\ast \ast }(y).$$

也就是说，对偶问题的价值函数 $v^{\star }(y)$ 是原问题的价值函数 $v(y)$ 的双重凸共轭，也称为 双共轭（biconjugate）。

所以，问题转化为：什么样的函数 $v(y)$ 满足它的双共轭就等于它自身？这一问题的答案由如下定理给出：

证明

一个函数是正常的（proper），当且仅当它从不取得 $-\mathrm{\infty }$ 的值，且不永远取得 $+\mathrm{\infty }$ 的值。

对于非正常函数的情形，可以验证 $f(x)\equiv +\mathrm{\infty }$ 和 $f(x)\equiv -\mathrm{\infty }$ 互为共轭。除此之外，只要 $f(x)$ 在任何一点处取到 $-\mathrm{\infty }$，必然有 $f^{\ast }(x^{\ast })\equiv +\mathrm{\infty }$。所以，满足 $f^{\ast \ast }=f$ 的非正常函数只有这两种情形。下面的讨论仅限于正常函数。对于正常函数，下半连续且凸的条件等价于它的上境图是闭凸集。

这一条件的必要性是容易的。因为 $f=f^{\ast \ast }$ 是 $f^{\ast }$ 的凸共轭，作为一系列线性函数的上确界，它的上境图必然是一系列闭凸集的交集，所以必然是闭凸集。这就说明，满足 $f^{\ast \ast }=f$ 的正常函数必然是下半连续且凸的。

反过来，这些条件也是充分的。和其他强对偶定理的证明一样，证明可以分为两步。

第一步，说明弱对偶成立，即 $f(x)\ge f^{\ast \ast }(x)$。由凸共轭的定义可知，对于所有 $x,x^{\ast }\in {\mathbf{R}}^d$，都有

$$f^{\ast }(x^{\ast })\ge x^{\ast }\cdot x-f(x).$$

这就说明，对于所有 $x,x^{\ast }\in {\mathbf{R}}^d$，同样有

$$f(x)\ge x^{\ast }\cdot x-f^{\ast }(x^{\ast }).$$

对不等式右侧中的 $x^{\ast }$ 取上确界，就有 $f(x)\ge f^{\ast \ast }(x)$。

第二步，利用 超平面分离定理 说明 $f(x)\le f^{\ast \ast }(x)$。假设不然，存在 $x_0\in {\mathbf{R}}^d$ 使得 $f(x_0)>f^{\ast \ast }(x_0)$ 成立。因为 $f(x)$ 的上境图 $\mathrm{epi}(f)$ 是闭凸集，而且单点集 $\{(x_0,f^{\ast \ast }(x_0))\}$ 是紧凸集，所以，根据超平面分离定理，存在 $(\lambda ,t)\in {\mathbf{R}}^d\times \mathbf{R}$ 和 $\alpha \in \mathbf{R}$ 使得对于所有 $x\in \mathrm{dom}f:=\{x\in {\mathbf{R}}^d:f(x)<+\mathrm{\infty }\}$ 和所有 $y\ge f(x)$ 都有

$$\lambda \cdot x-ty<\alpha <\lambda \cdot x_0-t{f}^{\ast \ast }(x_0)$$

成立。因为 $y$ 可以选得任意大，所以必然有 $t\ge 0$。这又可以分为两种情形。

首先，讨论 $t>0$ 的情形。此时，将不等式的各部分都同除以 $t$，并设 ${\lambda }^{\prime }=t^{-1}\lambda$ 和 ${\alpha }^{\prime }=t^{-1}\alpha$，就得到

$${\lambda }^{\prime }\cdot x-y<{\alpha }^{\prime }<{\lambda }^{\prime }\cdot x_0-f^{\ast \ast }(x_0).$$

对所有 $x\in \mathrm{dom}f$，令 $y=f(x)$，就都成立

$${\alpha }^{\prime }>{\lambda }^{\prime }\cdot x-f(x).$$

故而，对不等号右侧的 $x$ 取上确界，有

$${\alpha }^{\prime }\ge \underset{x\in {\mathbf{R}}^d}{sup}{\lambda }^{\prime }\cdot x-f(x)=f^{\ast }({\lambda }^{\prime }).$$

进而，有

$$f^{\ast \ast }(x_0)<{\lambda }^{\prime }\cdot x_0-f^{\ast }({\lambda }^{\prime })\le \underset{x^{\ast }\in {\mathbf{R}}^d}{sup}{x}^{\ast }\cdot x_0-f^{\ast }(x^{\ast })=f^{\ast \ast }(x_0).$$

这一矛盾说明 $t>0$ 的情形并不成立。

最后，讨论 $t=0$ 的情形。事实上，将要说明的是，可以通过微扰，将它转化为 $t>0$ 的情形。任取 ${\lambda }_0\in \mathrm{dom}{f}^{\ast }$，根据凸共轭的定义可知，对于任何 $x\in \mathrm{dom}f$ 和 $y\ge f(x)$ 都有

$${\lambda }_0\cdot x-y\le f^{\ast }({\lambda }_0).$$

因此，对于任意 $\epsilon >0$，都有

$$(\lambda +\epsilon {\lambda }_0)\cdot x-\epsilon y<\alpha +\epsilon f^{\ast }({\lambda }_0).$$

同时，因为 $\alpha <\lambda \cdot x_0$，所以，对于充分小的 $\epsilon >0$，又有

$$\alpha +\epsilon f^{\ast }({\lambda }_0)<(\lambda +\epsilon {\lambda }_0)\cdot x_0-\epsilon f^{\ast \ast }(x_0).$$

因此，如果取 ${\lambda }^{\prime }=\lambda +\epsilon {\lambda }_0$，$t^{\prime }=\epsilon$ 和 ${\alpha }^{\prime }=\alpha +\epsilon f^{\ast }({\lambda }_0)$，那么，就有

$${\lambda }^{\prime }\cdot x-t^{\prime }y<{\alpha }^{\prime }<{\lambda }^{\prime }\cdot x_0-t^{\prime }{f}^{\ast \ast }(x_0).$$

这就又回到了前一种情形，仍然会导致矛盾。

这一矛盾说明，并不存在满足 $f(x_0)>f^{\ast \ast }(x_0)$ 的点 $x_0\in {\mathbf{R}}^d$。故而，总有 $f(x_0)\le f^{\ast \ast }(x_0)$。

结合这两步证明的结果，就得到 $f^{\ast \ast }(x)=f(x)$ 成立。

因此，强对偶成立，当且仅当 $v(y)$ 是关于 $y\in {\mathbf{R}}^d$ 的凸函数²。

次梯度

上一节说明了，带惩罚的问题的价值函数 $h(\lambda )$ 是原问题的价值函数 $v(y)$ 的凸共轭的相反数。因为凸共轭的定义实际上是一个含参数的最优化问题，所以它也成立类似 包络定理 的结论。但是，因为凸函数并非处处可微的，所以需要首先将导数的定义推广到凸函数的情形。这就引出了次梯度的概念。

次梯度

对于凸函数 $f:{\mathbf{R}}^d\to \mathbf{R}\cup \{\pm \mathrm{\infty }\}$ 和 $x_0\in \mathrm{dom}f$，如果向量 $x^{\ast }\in {\mathbf{R}}^d$ 满足对于任何 $x\in {\mathbf{R}}^d$，都有

$$f(x)\ge f(x_0)+x^{\ast }\cdot (x-x_0),$$

那么，就称 $x^{\ast }$ 是 $f(x)$ 在 $x_0$ 处的一个 次梯度（subgradient）。函数 $f(x)$ 在 $x_0$ 处的全体次梯度的集合称为它在该处的 次微分（subdifferential），记作 $\partial f(x_0)$。

几何直观上，凸函数 $f(x)$ 在 $x_0$ 处的次微分，就是它在该处的所有支撑超平面的斜率向量的集合。对于一维的情形，次微分

$$\partial f(x_0)=[{\partial }_{-}f(x_0),{\partial }_{+}f(x_0)],$$

其中，${\partial }_{-}f(x_0)$ 和 ${\partial }_{+}f(x_0)$ 分别是函数 $f(x)$ 在 $x_0$ 处的左右导数。进一步地，对于整数集上的凸函数 $f:\mathbf{Z}\to \mathbf{R}\cup \{\pm \mathrm{\infty }\}$ 延拓而来的 $\tilde{f}(x)$，它在整数点 $x=k$ 处的左右导数就是左右两侧的一阶差分：

$$\partial \tilde{f}(k)=[f(k)-f(k-1),f(k+1)-f(k)].$$

显然，凸函数 $f(x)$ 在点 $x_0$ 处可微，当且仅当它在该处的次微分 $\partial f(x_0)$ 是单点集。

因为凸共轭提供了从支撑超平面的斜率向量到它的截距的映射，所以，利用凸共轭，可以判断一个斜率向量 $x^{\ast }$ 是否是凸函数 $f(x)$ 在给定点 $x$ 处的一个次梯度。

定理（凸共轭与次梯度）

对于正常凸函数 $f:{\mathbf{R}}^d\to \mathbf{R}$ 和任意 $x,x^{\ast }\in {\mathbf{R}}^d$，都有

$$x^{\ast }\in \partial f(x)⟺x^{\ast }\cdot x=f(x)+f^{\ast }(x^{\ast }).$$

进而，如果 $f$ 还是下半连续的，那么这两个条件都等价于 $x\in \partial f^{\ast }(x^{\ast })$。

证明

按照次梯度的定义，$x^{\ast }\in \partial f(x)$，当且仅当

$$f(x^{\prime })\ge f(x)+x^{\ast }\cdot (x^{\prime }-x),\mathrm{\forall }{x}^{\prime }\in {\mathbf{R}}^d.$$

这等价于

$$x^{\ast }\cdot x-f(x)\ge x^{\ast }\cdot x^{\prime }-f(x^{\prime }),\mathrm{\forall }{x}^{\prime }\in {\mathbf{R}}^d.$$

这又等价于

$$x^{\ast }\cdot x-f(x)\ge \underset{x^{\prime }\in {\mathbf{R}}^d}{sup}{x}^{\ast }\cdot x^{\prime }-f(x^{\prime })=f^{\ast }(x^{\ast }).$$

但是，依据凸共轭的定义，总是有

$$x^{\ast }\cdot x-f(x)\le f^{\ast }(x^{\ast }).$$

因此，前一式中的大于等于号实际上等价于等号，也就等价于下式

$$x^{\ast }\cdot x=f(x)+f^{\ast }(x^{\ast }).$$

这就完成了第一部分的证明。

对于 $f$ 是下半连续的正常凸函数的情形，依 Fenchel–Moreau 定理，有 $f^{\ast \ast }=f$。因此，这两个条件等价于

$$x^{\ast }\cdot x=f^{\ast }(x^{\ast })+f^{\ast \ast }(x).$$

再次应用第一部分的结论，它们也就等价于 $x\in \partial f^{\ast }(x^{\ast })$。

这一结论说明，如果 $f^{\ast \ast }=f$，那么凸共轭 $f^{\ast }$ 在 $x^{\ast }$ 处的次微分 $\partial f^{\ast }(x^{\ast })$，恰好就是斜率向量为 $x^{\ast }$ 的支撑超平面与上境图 $\mathrm{epi}f$ 的交点的 $x$ 分量的集合。

推论

对于下半连续的正常凸函数 $f:{\mathbf{R}}^d\to \mathbf{R}$ 和任意 $x,x^{\ast }\in {\mathbf{R}}^d$，都有

$$\begin{array}{rl}\partial f(x)& =\arg \underset{y^{\ast }\in {\mathbf{R}}^d}{max}x\cdot y^{\ast }-f^{\ast }(y^{\ast }),\\ \partial f^{\ast }(x^{\ast })& =\arg \underset{y\in {\mathbf{R}}^d}{max}{x}^{\ast }\cdot y-f(y).\end{array}$$

证明

下面，证明第二个等式。第一个等式的证明与之类似。

按照凸共轭的定义，有

$$f^{\ast }(x^{\ast })=\underset{y\in {\mathbf{R}}^d}{sup}{x}^{\ast }\cdot y-f(y),$$

所以，

$$x\in \arg \underset{y\in {\mathbf{R}}^d}{max}{x}^{\ast }\cdot y-f(y)$$

当且仅当 $f^{\ast }(x^{\ast })=x^{\ast }\cdot x-f(x)$，而这一等式成立，又当且仅当 $x\in \partial f^{\ast }(x^{\ast })$。这就证明了两个集合是相等的。

应用到本文的场景中，这一结论说明，求解问题

$$h(\lambda )=\underset{x\in X}{min}f(x)-\lambda \cdot g(x)=\underset{y\in g(X)}{min}v(y)-\lambda \cdot y$$

时，限制函数 $g(x)$ 在最优决策集合上的取值恰为 $\partial (-h(\lambda ))$。对于 $d=1$ 且问题只涉及整数的情形，这一集合就是区间

$$[h(\lambda -1)-h(\lambda ),h(\lambda )-h(\lambda +1)].$$

对于连续的整数 $\lambda$，这些区间首尾相接，所以，如果用于二分，只需要计算一侧的端点即可。

凸性证明

应用 WQS 二分的前提条件是价值函数的凸性。在算法竞赛中，可以通过打表、感性理解等方式猜测凸性成立。但是，严格地证明凸性成立，往往并不容易。本节结合如下经典题目，介绍算法竞赛中常见的证明凸性的方法。

这些方法粗略地可以分为四类：

• 归约为凸优化问题（包括 线性规划 等）的价值函数对参数的凸性，这包括建立 费用流 模型等方法；
• 利用状态转移方程也可以归纳地证明凸性成立，过程中可能会用到一些 保持凸性的变换；
• 对于区间分拆类型的问题，可以验证每段区间的成本函数满足 四边形不等式；
• 最后，对于特殊的问题，也可以通过交换论证直接说明凸性成立。

这些证明方法本身往往都同该问题的某种解法联系在一起。

归约为含参凸优化

考虑如下形式的含参凸优化问题：

$$v(y)=\underset{x\in \mathcal{D}(y)}{inf}f(x,y).$$

其中，目标函数 $f:{\mathbf{R}}^n\times {\mathbf{R}}^d\to \mathbf{R}\cup \{\pm \mathrm{\infty }\}$ 对于每个 $y\in {\mathbf{R}}^d$ 都是关于 $x\in {\mathbf{R}}^m$ 的凸函数，而可行域 $\mathcal{D}:{\mathbf{R}}^d\to \mathcal{P}({\mathbf{R}}^m)$ 是 ${\mathbf{R}}^d$ 上的集合值函数，且对于每个 $y\in {\mathbf{R}}^d$，集合 $\mathcal{D}(y)$ 都是凸集。这些条件保证了对于任意参数 $y\in {\mathbf{R}}^d$，这都是一个凸优化问题。

证明

对于任意 $y_1,y_2\in {\mathbf{R}}^d$ 和 $\alpha \in (0,1)$，需要证明

$$v(\alpha y_1+(1-\alpha )y_2)\le \alpha v(y_1)+(1-\alpha )v(y_2).$$

如果 $v(y_1)=+\mathrm{\infty }$ 或 $v(y_2)=+\mathrm{\infty }$，那么不等式的右侧就是 $+\mathrm{\infty }$，不等式必然成立。否则，$v(y_1)$ 和 $v(y_2)$ 都是有限值。对于任意 $\epsilon >0$ 和 $i=1,2$，都存在 $x_i\in \mathcal{D}(y_i)$ 使得 $f(x_i,y_i)<v(y_i)+\epsilon$ 成立。利用映射 $\mathcal{D}$ 的图像的凸性可知

$$\alpha x_1+(1-\alpha )x_2\in \mathcal{D}(\alpha y_1+(1-\alpha )y_2).$$

也就是说，$\alpha x_1+(1-\alpha )x_2$ 是参数为 $\alpha y_1+(1-\alpha )y_2$ 的最优化问题的一个可行解。利用最优化条件和目标函数的凸性可知

$$\begin{array}{rl}v(\alpha y_1+(1-\alpha )y_2)& \le f(\alpha x_1+(1-\alpha )x_2,\alpha y_1+(1-\alpha )y_2)\\ & \le \alpha f(x_1,y_1)+(1-\alpha )f(x_2,y_2)\\ & <\alpha v(y_1)+(1-\alpha )v(y_2)+\epsilon .\end{array}$$

因为 $\epsilon$ 的选取是任意的，令 $\epsilon \to 0$，就有

$$v(\alpha y_1+(1-\alpha )y_2)\le \alpha v(y_1)+(1-\alpha )v(y_2).$$

因此，价值函数 $v(y)$ 的凸性成立。

算法竞赛中，最为常见的凸优化问题就是线性规划问题。

推论

设 $c\in {\mathbf{R}}^n$，$A_1\in {\mathbf{R}}^{d_1\times n}$，$A_2\in {\mathbf{R}}^{d_2\times n}$，$y_1\in {\mathbf{R}}^{d_1}$，$y_2\in {\mathbf{R}}^{d_2}$。考虑如下含参线性规划问题：

$$v(y_1,y_2)=\underset{x\in {\mathbf{R}}^n}{min}c\cdot x\text{ subject to }{A}_{1}x\le y_1,A_{2}x=y_2,x\ge 0.$$

那么，价值函数 $v(y_1,y_2)$ 是关于 $(y_1,y_2)$ 的凸函数。

无论是不等式约束，还是等式约束，线性规划的价值函数都是约束条件参数的凸函数。

很多图论问题都可以写成线性规划问题的形式：

• 网络流问题：最大流、最小割、最小费用流；
• 无负环的最短路问题；
• 二分图的最大（权）匹配、最小点覆盖等问题；
• 一般图的最大（权）匹配问题；
• 最小生成树问题³。

因此，这些问题的价值函数都是这些问题的参数的凸（凹）函数。

例如，在费用流的语境下，有如下常见结论：

证明

设有向图 $G=(V,E)$，边 $(i,j)$ 的容量为 $c_{ij}$，单位流量的费用为 $w_{ij}$,，源点和汇点分别为 $s$ 和 $t$。记决策变量为 $\{f_{ij}\}$，其中，$f_{ij}$ 为边 $(i,j)\in E$ 的流量。那么，最小费用流可以写成如下线性规划问题：

$$\begin{array}{rl}v(m)=\underset{\{f_{ij}\}}{min}& \sum _{(i,j)\in E}{w}_{ij}{f}_{ij}\\ \text{subject to }& \sum _{(j,i)\in E}{f}_{ji}-\sum _{(i,j)\in E}{f}_{ij}=\{\begin{array}{ll}-m,& i=s,\\ m,& i=t,\\ 0,& \text{otherwise},\end{array}\mathrm{\forall }i\in V,\\ & 0\le f_{ij}\le c_{ij},\mathrm{\forall }(i,j)\in E.\end{array}$$

因此，最小费用 $v(m)$ 是参数 $m$ 的凸函数。

算法竞赛中很多问题都可以归约为网络流等图论问题，从而都可以通过类似的方式建立价值函数的凸性。

利用这一方法，可以得到种树问题的第一个凸性证明：

利用状态转移方程

尽管状态转移方程无法提供有效的计算方式，但是，它常常可以用于证明状态函数 $f(i,j)$ 对于参数 $j$ 具有凸性。具体地说，就是将 $f(i,\cdot )$ 这一函数视为 $i$ 处的状态，就可以将关于 $f(i,j)$ 的状态转移方程看作是关于 $f(i,\cdot )$ 的递推关系，从而可以归纳地证明每个 $f(i,\cdot )$ 都是凸函数。这类证明凸性的方法在 Slope Trick 优化 DP 的场景中更为常见，该页面也讨论了常见的保持凸性的变换。

这一方法同样可以用于证明种树问题的凸性：

凸性证明二

设 $f(i,j)$ 为前 $i$ 个坑种 $j$ 棵树时的最大收益。考察如下状态转移方程：

$$f(i,j)=max\{f(i-1,j),f(i-2,j-1)+a_i\}.$$

将这一状态转移方程看作是函数 $f(i,\cdot )$ 的递推关系式。因为最值符号内涉及两个不同的函数，这并不能表达为卷积上确界的形式。但是，仍然可以通过归纳的方法证明函数 $f(i,\cdot )$ 是凹函数。

实际上，需要归纳地证明如下两点：

• $f(i,j)-f(i-2,j-1)$ 关于 $j$ 递减；
• $f(i,j)-f(i-1,j)$ 关于 $j$ 递增。

归纳起点是平凡的。假设它们对于所有 $i-1$ 及之前的自然数都成立，现在证明它对 $i$ 也成立。直接验证即可。

首先，由归纳假设，有

$$f(i-1,j)-f(i-2,j-1)=(f(i,j)-f(i-2,j-1))-(f(i,j)-f(i-1,j))$$

关于 $j$ 递减。所以，有

$$f(i,j)-f(i-2,j-1)=max\{f(i-1,j)-f(i-2,j-1),a_i\}$$

关于 $j$ 递减，且

$$f(i,j)-f(i-1,j)=max\{0,a_i-(f(i,j)-f(i-2,j-1))\}$$

关于 $j$ 递增。这就完成了归纳。

进而，有

$$f(i,j)-f(i,j-1)=(f(i,j)-f(i-2,j-1))-(f(i,j-1)-f(i-1,j-1))-(f(i-1,j-1)-f(i-2,j-1))$$

关于 $j$ 递减。这就说明 $f(i,j)$ 是关于 $j$ 的凹函数，从而，价值函数 $v(m)=f(n,m)$ 是关于 $m$ 的凹函数。

这个证明的一个副产品是，对于任意 $i$，都存在 $p_i$ 使得

$$f(i,j)=\{\begin{array}{ll}f(i-1,j),& j\le p_i,\\ f(i-2,j-1)+a_i,& j>p_i.\end{array}$$

这说明，可以通过平衡树直接维护序列 $f(i,\cdot )$，复杂度是 $O(n{\log }^{2}n)$ 的。但是，好处是可以处理任意种树间隔的一般情形，且一次性地获得了所有 $v(m)$ 的值。

四边形不等式

算法竞赛中，另一类常见的成立凸性的问题是 区间分拆问题。该页面证明了，如果单个区间的成本函数满足四边形不等式，那么限制区间个数的区间分拆问题的最小成本是区间个数的凸函数。该页面同样提供了一些判断某个函数 $w(l,r)$ 是否满足四边形不等式的方法。最为直接的方法就是计算它的二阶混合差分：

$$\begin{array}{rl}{\mathrm{\Delta }}_l{\mathrm{\Delta }}_{r}w(l,r)& ={\mathrm{\Delta }}_l(w(l,r+1)-w(l,r))\\ & =w(l+1,r+1)-w(l+1,r)-w(l,r+1)+w(l,r).\end{array}$$

函数 $w(l,r)$ 满足四边形不等式，当且仅当 ${\mathrm{\Delta }}_l{\mathrm{\Delta }}_{r}w(l,r)$ 非正。直观上，满足四边形不等式的函数通常意味着，区间向两侧扩大——即左端点向左移动和右端点向右移动——具有某种协同效应。

种树问题同样可以看作是一个区间分拆问题，可以通过验证四边形不等式进行证明。

凸性证明三

在种树的收益序列前添加一个 $a_0$，它可以是任何值。然后，种树问题就等价于将序列 $\{a_0,a_1,\cdots ,a_n\}$ 分成 $m$ 段，且每段的收益函数为

$$w(l,r)=\underset{i\in [l+1,r]}{max}{a}_i$$

的区间分拆问题。也就是说，每一段的收益是除去第一棵树外，其余树的收益的最大值——这就保证了间隔种树。

因为这是最大化问题，需要验证「交叉大于包含」，即对于任意 $a<b<c<d$，都成立

$$w(a,c)+w(b,d)\ge w(a,d)+w(b,c).$$

代入收益函数的表达式，并设

$$A=\underset{i\in [a+1,b]}{max}{a}_i,B=\underset{i\in [b+1,c]}{max}{a}_i,C=\underset{i\in [c+1,d]}{max}{a}_i,$$

则要证明的不等式可以写作

$$max\{A,B\}+max\{B,C\}\ge max\{A,B,C\}+B.$$

注意到不等号左侧的两项 $max\{A,B\}$ 和 $max\{B,C\}$ 中较大的那个就等于 $max\{A,B,C\}$，而它们中较小的那个总是不小于 $B$，因此该不等式成立。

将种树问题转化为区间分拆问题后，只需要用 ST 表等方式预处理区间最值，可以单次 $O(1)$ 地计算单个区间的成本，就可以套用区间分拆问题的算法在 $O(n\log n\log L)$ 或 $O(n(n+m))$ 的时间复杂度内解决该问题。该方法同样可以处理任意种树间隔的问题。

交换论证

组合优化问题中，证明价值函数的凸性常常会用到交换论证（exchange argument）。具体地说，就是从参数为 $m-1$ 和 $m+1$ 的问题的最优解出发，通过交换部分元素，构造出参数为 $m$ 且价值不超过 $(v(m-1)+v(m+1))/2$ 的可行解，从而利用 $v(m)$ 的最优性来证明凸性的论证方法。相较于凸优化的情形，组合优化问题中并不存在自然地构造两个解的「中间形态」的方法，因此，交换论证的应用通常具有一定的技巧性。

「边际成本递增」并不一定导致凸性

组合优化问题中，目标函数常常具有一些「边际成本递增」的性质，但是这并不必然导致凸性。一个典型的例子是 [IOI 2005] Riv 河流，该问题的链上版本是满足四边形不等式因而具有凸性的，但是树上版本存在凸性不成立的例子。

用于刻画「边际成本递增」的一个常见性质是函数的超模性（supermodularity）。对于有限集合 $X$ 的子集族 $\mathcal{P}X$ 上的函数 $f:\mathcal{P}X\to \mathbf{R}$，如果它满足以下两条等价性质之一：

1. （交叉小于包含）对于任何子集 $A,B\subseteq X$，都有 $f(A)+f(B)\le f(A\cup B)+f(A\cap B)$ 成立；
2. （边际成本递增）对于任何子集 $A\subseteq B\subseteq X$ 以及 $x\in X\setminus B$，都有 $f(A\cup \{x\})-f(A)\le f(B\cup \{x\})-f(B)$ 成立；

就称函数 $f$ 是 超模的（supermodular）。但是，超模函数作为目标函数的最优化问题中，价值函数

$$v(m)=\underset{A\subseteq X}{min}f(A)\text{ subject to }|A|=m$$

未必 是 $m$ 的凸函数。究其原因，就是从子集大小分别为 $m-1$ 和 $m+1$ 的最优解，一般来说是无法构造出子集大小为 $m$ 且满足前述价值函数大小关系的可行解的。

交换论证提供了种树问题凸性的又一种证明方式。

凸性证明四

利用交换论证。设种 $m-1$ 棵树和种 $m+1$ 棵树的最优方案分别由 $\{x_i^{(m-1)}\}\in \{0,1{\}}^n$ 和 $\{x_i^{(m+1)}\}\in \{0,1{\}}^n$ 给出，其中，取值为 $1$ 表示该坑位种了一棵树，取值为 $0$ 表示该坑位没有种树。定义序列 $\{z_i\}\in \{0,\pm 1{\}}^n$ 满足

$$z_i=x_i^{(m+1)}-x_i^{(m-1)},i=1,\cdots ,n.$$

这个序列标记了两个种树方案的差异。这一序列中取值为 $0$ 的位置表示该坑位要么在两个方案中都种了一棵树，要么在两个方案中都没有种树；而取值为 $-1$ 和 $+1$ 的位置则分别表示只在方案 $x^{(m-1)}$ 或只在方案 $x^{(m+1)}$ 中，该坑位种了一棵树。因为任何方案中都不能在相邻的坑位种树，所以有如下观察：

• 连续的非零子段中，$z_i$ 的取值必然在 $\pm 1$ 之间相互交错的；
• 极大的连续非零子段左右两侧的 $0$，必然表示在两个方案中都没有种树。

因此，如果某个极大的连续非零子段中，$z_i$ 的和恰好为 $+1$，也就是说，在该段坑位中，方案 $x^{(m+1)}$ 比方案 $x^{(m-1)}$ 多种了一棵树，那么就可以在该段内交换两个方案的种树位置。这样，就得到了两个各种 $m$ 棵树的可行方案。因为没有改变两个方案中总的种树的位置和数量，只是将它们重新分配，所以总的收益不变，仍然是 $v(m-1)+v(m+1)$。但是，这两个种 $m$ 棵树的方案未必是最优的，因此，它们各自的收益不会超过 $v(m)$。这就证明了

$$v(m-1)+v(m+1)\le 2v(m),$$

也就是说，$v(m)$ 是关于 $m$ 的凹函数。

现在，只剩下一个问题，就是和恰好为 $+1$ 的极大连续非零子段是否存在。因为是若干个交错的 $\pm 1$ 相加，一个连续非零子段的和只能是 $0$ 或 $\pm 1$。又因为所有这些极大连续非零子段的和等于 $2$，所以，一定存在至少两个和恰好为 $+1$ 的极大连续非零子段。这就完成了证明。

例题

本节介绍几个不同场景下应用 WQS 二分方法的例题。

模板题目

解答

与前文讨论的种树问题稍有不同，本题要求至多种 $m$ 棵树，而非恰好种 $m$ 棵树。仍然用 $v(m)$ 表示前文讨论的种树问题的价值函数，本题的答案实际上是 $\tilde{v}(m)=\underset{k\le m}{max}v(k)$。因为 $v(m)$ 是凹函数，也就是一个单峰函数，本题的答案相当于只保留 $v(m)$ 上升至峰顶的部分，然后函数会一直留在峰顶；这相当于仅仅保留切线斜率非负的部分。因此，本题与前文讨论的题目的唯一差别，就是 WQS 二分时，初始的斜率范围为 $[0,\underset{i}{max}{a}_i]$ 而非 $[\underset{i}{min}{a}_i,\underset{i}{max}{a}_i]$。

应用 WQS 二分的方法移除数量限制后，问题转化为计算链上最大权独立集，只是将原本的收益 $\{a_i\}$ 替换为了 $\{a_i+k\}$。这是经典的动态规划题目。可以设 $f(i,j)$ 为第 $i$ 个坑位选择种树（$j=1$）或不种树（$j=0$）时，前 $i$ 个树坑的子问题的最大收益。由此，可以写出状态转移方程为

$$\begin{array}{rl}f(i,0)& =max\{f(i-1,0),f(i-1,1)\},\\ f(i,1)& =f(i-1,0)+a_i+k.\end{array}$$

初始条件为 $f(0,0)=0$ 和 $f(0,1)=-\mathrm{\infty }$，最终答案为 $max\{f(n,0),f(n,1)\}$。单次计算复杂度为 $O(n)$，整体时间复杂度为 $O(n\log L)$，其中，$L=\underset{i}{max}|a_i|$。

参考实现如下：

传统方法对偶方法

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75

#include <algorithm> #include <cstring> #include <iostream> #include <tuple> #include <vector> int main() { int n, m; std::cin >> n >> m; std::vector<int> a(n + 1); for (int i = 1; i <= n; ++i) std::cin >> a[i]; // Calculate h(k) = max_x f(x) - k * g(x). // Meanwhile, obtain the maximum value g(x) of the optimizer x. auto calc = [&](int k) -> std::pair<long long, int> { long long dp[2] = {0, -0x3f3f3f3f3f3f3f3f}; int opt[2] = {0, 0}; for (int i = 1; i <= n; ++i) { long long tmp_dp[2]; int tmp_opt[2]; if (dp[0] > dp[1]) { tmp_dp[0] = dp[0]; tmp_opt[0] = opt[0]; } else if (dp[1] > dp[0]) { tmp_dp[0] = dp[1]; tmp_opt[0] = opt[1]; } else { tmp_dp[0] = dp[0]; tmp_opt[0] = std::max(opt[0], opt[1]); } tmp_dp[1] = dp[0] + a[i] - k; tmp_opt[1] = opt[0] + 1; std::memcpy(dp, tmp_dp, sizeof(dp)); std::memcpy(opt, tmp_opt, sizeof(opt)); } long long val; int opt_m; if (dp[0] > dp[1]) { val = dp[0]; opt_m = opt[0]; } else if (dp[1] > dp[0]) { val = dp[1]; opt_m = opt[1]; } else { val = dp[0]; opt_m = std::max(opt[0], opt[1]); } return {val, opt_m}; }; // WQS binary search. long long val, tar_val; int opt_m, tar_k; std::tie(val, opt_m) = calc(0); if (opt_m <= m) { // Have already reached the peak. tar_k = 0; tar_val = val; } else { // Find the maximum k such that g(x) >= m. int ll = 0, rr = 1000000; while (ll <= rr) { int mm = (ll + rr) / 2; std::tie(val, opt_m) = calc(mm); if (opt_m >= m) { tar_k = mm; tar_val = val; ll = mm + 1; } else { rr = mm - 1; } } } long long res = tar_val + (long long)tar_k * m; std::cout << res << std::endl; return 0; }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67

#include <algorithm> #include <iostream> #include <tuple> #include <type_traits> #include <vector> // Golden section search on integer domain (unimodal function) template <typename T, typename F> typename std::enable_if< std::is_integral<T>::value, std::pair<T, decltype(std::declval<F>()(std::declval<T>()))>>::type golden_section_search(T ll, T rr, F func) { constexpr long double phi = 0.618033988749894848204586834L; T ml = ll + static_cast<T>((rr - ll) * (1 - phi)); T mr = ll + static_cast<T>((rr - ll) * phi); auto fl = func(ml), fr = func(mr); while (ml < mr) { if (fl > fr) { rr = mr; mr = ml; fr = fl; ml = ll + static_cast<T>((rr - ll) * (1 - phi)); fl = func(ml); } else { ll = ml; ml = mr; fl = fr; mr = ll + static_cast<T>((rr - ll) * phi); fr = func(mr); } } T best_x = ll; auto best_val = func(ll); for (T i = ll + 1; i <= rr; ++i) { auto val = func(i); if (val > best_val) { best_val = val; best_x = i; } } return {best_x, best_val}; } int main() { int n, m; std::cin >> n >> m; std::vector<int> a(n + 1); for (int i = 1; i <= n; ++i) std::cin >> a[i]; // Calculate h(k) = max_x f(x) + k * g(x). auto calc = [&](int k) -> long long { long long dp[2] = {0, -0x3f3f3f3f3f3f3f3f}; for (int i = 1; i <= n; ++i) { std::tie(dp[0], dp[1]) = std::make_pair(std::max(dp[0], dp[1]), dp[0] + a[i] + k); } return std::max(dp[0], dp[1]); }; // Solve the dual problem to find v(m). // Implemented as a minimization problem by adding negative signs. // Only consider tangent lines of negative slopes to ignore the part // of the curve after the peak. auto res = -golden_section_search(-1000000, 0, [&](int k) -> long long { return -calc(k) + (long long)k * m; }).second; std::cout << res << std::endl; return 0; }