0%

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\) 的值:

  1. \(e < L\) ,则转移的 \(t\)\(L\)
  2. \(R < e\) ,则转移的 \(t\)\(R\)
  3. 否则转移的 \(t\)\(e\)

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

我们把每个 \(j\) 对应的合法区间画出来,有两种可能:

Sorry, the picture can't be loaded Sorry, the picture can't be loaded

左图表示 \(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\) 是非降的,一路维护过来就好了。