合并香蕉

· · 题解

记第 i 个香蕉参与合并的次数为 c_i，我们所需做的就是最大化 \sum _ {i = 1} ^ n a_i k_i ^ {-c_i}。

Hint：最优的合并策略中，必然有 \{c_1, c_2, \cdots, c_n\} = \{1, 2, 3, \cdots, n - 1, n - 1\}。

证明：使用调整法。考虑合并形成的最优二叉树，设其不满足上述性质，则必然存在至少两个节点，满足其两个儿子均为叶子节点。则这样的节点中深度次深的 x，记其两个儿子为 a, b；再取与 x 同深度的另一节点 y，记其两个儿子为 c, d。由于 x 是次深的，因此 y 必然存在，且 c, d 中至少有一个是叶子节点，不妨设其为 c。

接下来，记 v_x = a_x k_x ^ {-c_x}，则在原树中，a, b, c 三点对答案的贡献即为 v_a + v_b + v_c。注意到，这里的 a, b, c 可以随意进行调换，因此我们不妨设 (1 - \frac 1 {k_c}) v_c \ge \max((1 - \frac 1 {k_a}) v_a, (1 - \frac 1 {k_b}) v_b) 最大。我们作形如这样的调整：将 d 的整个子树插入到上方，使其成为 x 的兄弟。注意到，此时 d 子树的深度完全没有发生变化，而 c 的深度减少 1，a, b 的深度增加 1，从而 a, b, c 对答案的贡献变为 \frac {v_a} {k_a} + \frac {v_b}{k_b} + v_ck_c。与原来的贡献相减，得到 \Delta = (k_c - 1)v_c - ((1 - \frac 1 {k_a}) v_a + (1 - \frac 1 {k_b}) v_b)。而注意到 (k_c - 1)v_c = k_c (1 - \frac 1 {k_c})v_c \ge 2 (1 - \frac 1 {k_c})v_c \ge (1 - \frac 1 {k_a}) v_a + (1 - \frac 1 {k_b}) v_b，也即 \Delta \ge 0。因此，这样的调整总会让答案不劣。同时，注意到每次调整后，所有叶子节点的深度和总会 +1，这说明我们的调整过程是单调的，最终总能使其到达 Hint 中所描述的状态。故证毕。

回到原题，现在我们已经知道可重集 \{c_1, c_2, \cdots, c_n\}，我们只需对每个 i 分配对应的 c_i。如果暴力进行二分图最大权匹配，未免代价有些太过高昂。注意到，当 c_i \ge 50 时，有 n a_i k_i ^ {- c_i} \le 10 ^ 5 \cdot 10 ^ 5 \cdot 2 ^ {-50} < \epsilon = 10 ^ {-5}，因此我们只需保留右部的 O(\log V) 个点。进一步的，我们发现在 k_i 相同时，a_i 较大的点被分配到的 c_i 一定较小，因此我们对于同一个 k_i 也只需保留前 50 大的 a_i。这样左部点的数量也被压缩到了 O(k \log V)。而在这张图上跑费用流的复杂度即为 O(k\log V \cdot k \log ^ 2 V \cdot \log V) = O(k ^ 2 \log ^ 4 V)，足以通过。