小朋友问我的一道题，然后我就看题解了。

原题解写的不任职时，但是 comment 写的还算清楚。可以借鉴一下 comment 的思想然后就可以自己 YY 了。

Problem

现在有 $n$ 个馅饼，第 $i$ 个馅饼的价格是 $a_i$ 。每买一个价格为 $k$ 的馅饼，你就可以免费得到一个价格严格小于 $k$ 的馅饼。求购买所有的馅饼的最小总价格。

Solution

要使得最后总价格最小，就是要使得免费获得的馅饼的价格和最大。

还是用 dp 来引入吧。

将所有数从大到小排序，可以得到若干个二元组 $<val, count>$ 表示 $val$ 这个价格的馅饼出现了 $count$ 次。按照 $val$ 从大到小排序后，每次处理出一个二元组。令 $f_{i, j}$ 表示处理完前 $i$ 个二元组后，且有不超过 $j$ 个馅饼是免费获得的时，免费获得的馅饼最大价格和。

转移思路很简单，就是前枚举当前二元组中有多少个是 free 。

$$f_{i + 1, j} = \max_{valid\ t} (f_{i, t} + (j - t) v_i)$$

注意这里的 $t$ 要求是合法的。于是就有一个非常简单的 $O(n^3)$ dp 了（终于可以写拍了）。什么情况下 $t$ 才是合法的呢，首先为了保证 $f_{i, t}$ 的合法，要求 $0 \leq t \leq T_i$ 其中 $T_i = \sum_j count$ 。为了保证 $j - t$ 的合法，要求 $0 \leq j - t \leq \min(count, T_i)$ 。所以有 $\max(0, j - count) \leq t \leq \min(j, T_i - j)$ 。我们发现，对于相同的 $i$ ， $j$ 与 $j +1$ 的区间相差为 $O(1)$ ，所以这个 dp 可以很轻松优化到 $O(n^2)$ 。当然你要写个 $O(1)$ 的 RMQ 也是可以直接做到 $O(n^2)$ 的。

$f$ 有个重要性质： $f_i$ 是凸的。虽然怎么证明还没想，但是感觉是对的。（你把 $f_{i, j + 1} - f_{i, j}$ 想成是边际收益就好了嘛）

如何利用这个性质呢？我们观察 $f$ 的转移：

$$f_{i + 1, j} = j v_i + \max_{valid\ t} (f_{i, t} - t v_i).$$

前面一部分对于 $j$ 来说是固定的，后面一部分是不是看着很面熟？似乎在各种什么斜率优化上啊，凸包上啊都可以看到这货。由于 $f$ 的凸性，我们可以保证 $f_{i, t} - t v_i$ 是单峰的，所以必然存在一个最大值，我们不妨设 $t = e$ 时取得最大值。

再来看 $j$ 对应的合法的 $t$ 的区间 $[L, R]$ ，其中 $L = \max(0, j - count), R = \min(j, T_i - j)$ 。我们可以直接通过区间推出最优的 $t$ 的值：

1. 若 $e < L$ ，则转移的 $t$ 为 $L$ ；
2. 若 $R < e$ ，则转移的 $t$ 为 $R$ ；
3. 否则转移的 $t$ 为 $e$ 。

所以我们还是得到一个 $O(n^2)$ 的 dp ，但是更加好写了。

我们把每个 $j$ 对应的合法区间画出来，有两种可能：

左图表示 $e + count < T_i - e$ 的情况，右图表示 $e + count > T_i - e$ 的情况。对于这两种情况，我们都可以把它们分成三部分：

两个图的第一部分均为 $1 \leq j < e$ 。这时候的区间为 $[\max(0, j - count), j]$ ，转移的 $t$ 为 $j$ ，代入后可以直接得到

$$f*{i + 1, j} = f*{i, j}.$$

两个图的第二部分均为 $e \leq j \leq \min(e + count, T_i - e)$ 。这时候有 $\max(0, j - count) \leq e \leq \min(j, T_i - j)$ ，故转移的 $t$ 为 $e$ ，代入后有

$$f_{i + 1, j} = j v_i + (f_{i, e} - e v_i).$$

左图的第三部分为 $e + count < j$ 。此时有 $e < \max(0, j - count)$ ，故转移的 $t$ 为 $\max(j - count, 0) = j - count$ ，可以写出转移为

$$f_{i+1, j}f_{i, j - count} + count v_i.$$

注意 $count v_i$ 与 $j$ 是无关的。

右图的第三部分为 $T_i - e < j$ 。此时 $\min(T_i - j, j) < e$ ，故有转移的 $t$ 为 $T_i - j$ ，可以写出转移为

$$f*{i+1, j} = f*{i, T_i - j} + (2j - T_i)v_i.$$

令 $g_{i, j} = f_{i, j} - f_{i, j - 1}$ 。只要知道了 $g$ ， $f$ 是很容易求出来的。我们观察一下 $g_i$ 与 $g_{i + 1}$ 的关系。对于两个图第一部分，我们有 $g_{i + 1, j} = g_{i, j}$ 。对于两个图的第二部分，我们有 $g_{i + 1, j} = v_i$ 。对于 $j = e$ 的特殊情况，代入可知仍然满足。对于左图的第三部分，我们有 $g_{i + 1, j} = g_{i, j - count}$ ；对于右图的第三部分，我们有 $g_{i + 1, j} = 2v_i - g_{i, T_i - j}$ 。

如何维护 $g_i$ 呢？再次注意到 $f$ 的凸性，在 $i$ 固定的情况下， $g_i$ 是非增的。于是可以直接用一个 multiset 来维护了。对于左图所示情况，直接插入 $count$ 个 $v_i$ 即可。对于右图所示情况，我们暴力求出所有 $j > e$ 的 $g_{i, j}$ ，直接塞入 multiset 里去。为什么这样可以过，我还没仔细想……

还有一个问题，如何求 $e$ ？注意到，在 $j$ 固定的情况下， $g_{i, j}$ 是非降的，而我们每次比较的值却是越来越小的，也就是说 $e$ 是非降的，一路维护过来就好了。