常学常新的 DP 凸优化（WQS 二分 & 斜率优化）

由于我实在太蠢了，所以我学了三次 WQS 二分。第一次我只会模仿着题解搞些二分，减去 $\mathrm{mid}$ 之类的操作，根本没懂原理。第二次学我知道了他是去截一个凸包，但是凸包斜率之类究竟是怎么来的还是不懂。第三次学就是这次了。

考虑有下面这个问题：

有 $n$ 个物品，$i$ 号物品有价值 $a_i>0$。从前往后选择恰好其中 $m$ 个物品，操作的价值为 物品的价值 $\times$ 上一个取的物品的编号，求最大操作价值。

考虑 DP。设 $f_i$ 表示考虑前 $i$ 个物品已经选了 $k$ 个，则有转移方程 $f_{i,k}=\underset{j=1}{\overset{n}{max}}{a}_i\times j+f_{j,k-1}$，时间复杂度 $O(n^{2}m)$。

1. WQS 二分

WQS 二分通常用于解决限制恰好选中若干个的问题，设 $f(m)$ 表示恰好取 $m$ 个时的答案，若 $(m,f(m))$ 构成凸包，则可以使用 WQS 二分，关于证明凸包可以打表或感性理解。

对于这个问题，可以发现他是上凸的，要求恰好取 $m$ 个，可以设法让取第 $(m+1)$ 个时，对答案贡献为负，因此设 $g(\lambda )=\underset{k}{max}(f(k)-\lambda k)$，表示每取一次，造成 $\lambda$ 的惩罚的情况下，最优的答案。引入平面直角坐标系，则有 $f(k)=\lambda k+g(\lambda )$，即 $g(\lambda )$ 是一条过点 $(k,f(k))$ 且斜率为 $\lambda$ 的直线的截距，由于 $(k,f(k))$ 构成上凸包，因此直线与凸包的切点 $k$ 随 $\lambda$ 的增大而减小，所以二分 $\lambda$，然后做 DP $f_i=\underset{j=1}{\overset{n}{max}}(a_i-\lambda )\times j+f_j$ 即可求得 $g(\lambda )$，时间复杂度优化到 $O(n^2\log n)$。

2. 斜率优化的几何理解

时间复杂度的瓶颈在于 $max$ 每次要 $O(n)$，通过代数方法可以进行斜率优化，此外还可以通过几何方法理解。

为简洁，记待优化方程为 $f_i=\underset{j=1}{\overset{n}{max}}j\times a_i+f_j$，同理考虑有若干个 $(j,f_j)$ 的点供 $f_i$ 选择，则有 $f_j=-a_i\times j+f_i$，即 $f_i$ 是斜率为 $-a_i$ 的直线的截距，要求 $f_i$ 最大，则可得不构成上凸包的点永远不会成为答案的一部分，因此使用单调队列存储相邻两个点的连成的直线的斜率和截距（即用单调队列维护这个上凸包，存这两个信息可以通过斜率比较前后直线是否构成凸包，也可以通过横坐标还原这两个点的信息），并在单调队列上二分即可，时间复杂度 $O(n{\log }^{2}n)$。