wqs 二分可以优化一些 dp，最常见的是 ”选一些物品，次数有限制，使总价值最大“，有以下限制：

• 定义 \(g(k)\) 为恰好用 \(k\) 此操作能获得的最大收益，那么 \(g(k)\) 要满足上凸。

• 如果不考虑限制，可以比较快地求出答案。

前置

股票买卖Ⅰ

有 \(n\) 天，每天股票有一个价值 \(a_i\)，但是每次手里只能有一支股票，每买卖一次需要花 \(c\) 的手续费，求最大价值。

首先有个很明显的 dp 做法，\(dp_{i,0/1}\) 代表第 \(i\) 天时手里 没有/有 股票的最大价值，答案就是 \(dp_{n,0}\)。

但是还有一个反悔贪心的做法，我们先让第一天强制买入，然后对于当前，假设股票价值为 \(q\) 考虑以下操作：

1. 如果上次操作是 ”买入 \(p\) 价值的一个股票“：

如果 \(q < p\)，那么买贵了，我们改成 ”买入 \(q\)“。

如果 \(q > p + c\)，那么卖了可以赚钱，我们添加一个 ”卖出 \(q\)“。

2. 如果上次操作是 ”卖出 \(p\)“：

如果 \(q > p\)，那么卖便宜了，改成 ”卖出 \(q\)“。

如果 \(q < p - c\)，那么我们添加一个 ”买入 \(q\)“。因为如果 \(q \ge p - c\)，那么后面卖出一个 \(r\) 的时候，不如把 ”卖出 \(p\)“ 改成 ”卖出 \(r\)“，这样更优。

正题

股票买卖Ⅱ

有 \(n\) 天，每天股票有一个价值 \(a_i\)，但是每次手里只能有一支股票，只能进行 \(k\) 次交易，求最大价值。

首先很显然可以 dp 求解，复杂度 \(O(nk)\)。而使用 wqs 可以得到一个 log 的算法。

思考费用流，发现这个东西根据 SSP 的费用流增广办法，增广路价值肯定是单减的。

所以我们把 $g(k) = $ 恰好 \(k\) 次操作能得到的最大值 这个东西的图像画出来，大概是这样的：

那么我们现在考虑随机选择一个价值 \(c\)，每次交易需要 \(c\) 的手续费。

那么假设我们有手续费时最优解为 \(ans\)，那么会有 \(ans + p\times c = g(p)\)，注意到这个函数是一个凸包，所以你可以认为有一个斜率为 \(c\) 的直线去切这个凸包，切出来的就是最大值，我们这个时候就可以无视交易次数的限制，就转化为 股票买卖Ⅰ。

然后我们可以二分斜率 \(c\)，就可以求出在 \(k\) 点切时最优的 \(ans\)，就可以反求 \(g(k)\) 了。

但是问题在于，我们现在可能有多点共线，那么我们就想要最小操作次数的那个位置，在解决 股票买卖Ⅰ 的时候，我们就要避免收入为 0 的买卖，这样就是最小的。

然后对于这个题，我们如果想要操作次数小于等于 \(k\) 的，那么我们可以把二分斜率的下界改成 \(0\)，这样就一定是最大的了。