CF2165B Marble Council

Cute_Fish · 2025-12-18 16:08:14 · 题解

考虑 check 一个集合是否合法，推广 P12029 的结论，当一个集合 S 合法，当且仅当 \max_{i \notin S} cnt_i \le \sum_{i \in S} cnt_i。

证明：对于不在集合 S 的元素，一定要把它分配到这些在 S 的元素所代表的集合中，使得在每一个集合，其一定不能强制替代掉那个属于 S 的元素。

注意到 \max_{i\in S} cnt_i \le \sum_{i\in S}cnt_i 故简单放缩一下得 \max cnt_i \le \sum_{i\in S}cnt_i。

设 f_{i,j} 表示考虑到大小为 i 的元素，和为 j 的方案数，背包转移即可。

时间复杂度 O(n^2)。