带权二分
- dp是凸的
- 二分切线（斜率）
在有数量限制的dp下，有三类模型：
- $f[n]$ 表示从 $n$ 个物品中选取任意多个后最大的价值和
- $f[n,k]$ 表示从 $n$ 个物品中选取恰好 $k$ 个后最大的价值和
- $f[n,k]$ 表示从 $n$ 个物品中选取至多 $k$ 个后最大的价值和
这里先讨论第二类模型
若物品之间相互无影响，则 $f[n,k]$ 必定是从按照价值排序后的所有物品中选取前 $k$ 大，则：
$$
\begin{aligned}
\forall k, s.t.
f[n,k]-f[n,k-1] &= a[k] \\
&\ge a[k-1] \\
&=f[n,k-1]-f[n,k-2]
\end{aligned}
$$
也就是说dp是凸的
那么可以选择一系列递增的斜率 ${s_n}$ 使得斜率 $s_k$ 对应恰好选择 $k$ 个物品的最优解（当然不一定是双射，不过不影响）
对于 $s_k$，考虑以它为斜率的直线和凸包的切点 $(k,y_k)$，也就是说 $s_k=f’[n,k]$
由于 $f’’ \ge 0$，所以 $f’[n,k]-s_k$ 单调递增
于是 $f[n,k]-s_kk+C$ 的最大值点就是 $x=k$ 时取到
这相当于每选一个物品就要付出代价 $s_k$ 时的最优解
也就是说原先需要记录两维的dp问题可以转化为一维问题，但要二分一个权值 $s_k$
若dp是上凸的，则：
- 恰好为 $k$ 时的二分范围：$[-\infty,+\infty]$
- 至多为 $k$ 时的二分范围：$[0,+\infty]$
Chef and Bitwise OR Operation
- 给定一个长度为 $n$ 的序列，现在你需要将这个序列划分成连续的 $k$ 段
- 每一段的贡献是这一段所有数的按位或
- 现在请求出最大的贡献
- $1 \le n \le 5000, 1 \le k \le n, 0 \le a_i \le 2^{30}$
$$
\begin{cases}
f[i,j]=\max _ {k < i} { f[k,j-1]+w[k+1,i] } \\
w[i,j]=\mathrm{BITOR}_{k=i}^{j}a[k]
\end{cases}
$$
那么这个dp是凸的嘛？
也就是说是否满足：$f[n,k]-f[n,k-1] \le f[n,k-1]-f[n,k-2]$
感性理解：分割的段数越多，贡献和越大，但增长的越慢（逐渐趋向于单独一组）
抽象化的问题：
给定 n 个物品，从中选择 m 个物品使得收益最大
- 设 $g(x)$ 表示恰好选择 $x$ 个物品所得到的最大收益，目标是求出 $g(m)$，如果它是一个凸函数的话，则可以进行凸优化，为了简便起见，假设最优化的是最大收益，且 $g(x)$ 上凸
- 那么可以得到 $g’(x)$ 是一个单调递减的函数，且 $g(x)$ 的最大值在 $g’(x)=0$ 处取到，假设这个值为 $x_0$
- 于是可以二分一个权 $k$，表示每选择一个物品，那么会额外付出代价 $k$，构造函数 $f(x)=g(x)-kx$，由于 $g(x)$ 和 $-kx$ 都是凸的，因此 $f(x)$ 依旧是凸的，即 $f’(x)=0$ 的时候 $f(x)$ 取得最大值
- 假设 $f(x)$ 在 $f’(x)=g’(x)-k=0 \Leftrightarrow g’(x)=k$ 的时候取得最大值，此时 $x$ 为 $x_1$
- 由于 $g’(x)$ 是单调函数，所以随着 $k$ 的变化 $x_1$ 随着单调变化，即随着 $k$ 变小，$x_1$ 也会变大
- 换而言之，实际上是用一条斜率为 $k$ 的直线来切这个 $g(x)$ 构成的凸包
- 于是可以二分 $k$ 来得到 $x_1$，从而适当调整 $k$ 的取值
[国家集训队]种树
给定 $n$ 个物品，从中选择 $m$ 个物品使得收益最大，其中 $g(x)$ 上凸
- 二分的 $k$ 的取值范围是 $(-\infty, \infty)$，在 $x_1 \le m$ 的时候记录 $k$，同时将 $k$ 往小调整，否则将 $k$ 往大调整
- 输出答案的时候用最后一次记录的 $k$ 进行计算
种树
给定 $n$ 个物品，从中选择 最多 $m$ 个物品使得收益最大，其中 $g(x)$ 上凸
由于是“最多”的限制，因此不能再像之前一样设置二分边界了，此时应该设为 $[0, \infty)$
此时当 $m \le x_0$ 的时候，最优解斜率在二分边界之内，因此可行，当 $m > x_0$ 的时候，最优解应在 $x=x_0$ 处取到，此时最优解的斜率为 $0$，依然在二分边界之内
