考虑把所有数从大到小加入，转移就是集合中的所有点权 $+1$，或者加入一个新的点。时间复杂度 $O(2^nns)$。
进一步的，这个问题等价于选择大小总和为 $s$ 的若干集合，要求前一个是后一个的子集，最大化所有集合的边数之和。显然如果两个集合互不包含，则一定是不优的，因此可以去掉子集的限制，从而转化成 $n$ 个物品，容量为 $s$ 的背包问题。时间复杂度 $O(2^nn+ns)$。
QOJ.ac
QOJ
As we are currently experiencing an overwhelming number of web requests for fetching user submissions, we have temporarily disabled the full submissions list. You must now be logged in to view submissions.
Discussion #212 for Problem #7600. Minimums on the Edges
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2025-12-13 00:14:58
Last updated: 2025-12-13 00:15:01
题解
Comments
No comments yet.