题解

思路

集合价值

设某个非空颜色集合的球数总和为 $S$，其中最大的球数为 $M$。

每组最多放两个球，所以至少需要 $\lceil S/2\rceil$ 组；同一种颜色的两个球不能同组，所以数量最多的颜色又要求至少 $M$ 组。反过来，总能把其他颜色的球尽量与最大颜色配对，剩余球再两两配对，因此集合价值恰为

做法

子任务 1

当所有 $a_i=1$ 时，只需按集合大小 $k$ 分类。大小为 $k$ 的集合有 $\binom nk$ 个，价值为 $\lceil k/2\rceil$。预处理阶乘和逆阶乘即可在线性时间内求和。

子任务 2

当 $n\le20$ 时，枚举全部颜色子集，直接统计每个子集的 $S$ 与 $M$，累加上式。

完整算法

将 $a_i$ 从小到大排序。考虑当前元素 $x$，以及只从此前元素中选择、球数和为 $s$ 的子集。加入 $x$ 后，$x$ 一定是这个集合中最后加入的最大值，因此它对答案的贡献为

用一维背包维护此前元素组成每个和 $s$ 的子集数量。处理 $x$ 时，先枚举所有已有的 $s$ 并累加贡献，再做从大到小的背包转移

每个非空子集都有唯一的最后一个下标，所以它恰好在处理该下标时被计入一次。

正确性证明

对任意非空颜色集合，令排序后下标最大的已选颜色球数为 $x$，其余已选颜色的球数和为 $s$。因为数组已排序，$x$ 就是该集合的最大球数，集合价值等于 $\max(x,\lceil(s+x)/2\rceil)$。

背包中的 $dp_s$ 恰好统计了从 $x$ 之前的颜色中选出、球数和为 $s$ 的方案数，因此算法会以正确价值计入所有以当前下标为最后下标的集合。每个非空集合的最后下标唯一，故所有集合都被计入且恰好计入一次，最终答案正确。

复杂度

记 $A=\sum a_i\le5000$。完整算法的时间复杂度为 $O(nA)$，空间复杂度为 $O(A)$。