[ABC184F] Programming Contest 分析

__ryp__ · 2023-12-17 14:11:14 · 个人记录

本题是要求序列中的 \max \sum\limits_{i=0}^{\lvert x\rvert -1 } A_{x_i} \le T。

注意到 N \le 40，无法直接进行子集枚举。但是如果我们将其分为两半，那么 N' \le 20，这时进行子集枚举可行。

于是我们就在 A =T_1, \cdots, T_{\lfloor N/2\rfloor} 与 B =T_{\lceil N/2\rceil}, \cdots, T_N 上进行子集枚举，求出每种状态的和。

最后，我们将两个子问题的解组合在一起：在其中一个子集上进行遍历：对 A_i，我们需要找到一个 B_j 使得 A_i + B_j 最大且小于等于 T。

这就是 upper_bound 的上一个元素。用指针就是 upper_bound (...)[-1]。取最大值即可。

源代码