Codeforces-326F
小朋友问我的一道题，然后我就看题解了。
原题解写的不任职时，但是 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\) 的值：
- 若 \(e < L\) ，则转移的 \(t\) 为 \(L\) ；
- 若 \(R < e\) ，则转移的 \(t\) 为 \(R\) ；
- 否则转移的 \(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\) 是非降的，一路维护过来就好了。