Gravatar
梦那边的美好ET
积分:6982
提交:1285 / 2720
暴力是O(3^N)。
考虑meet-in-the-middle,左边的那些3^(N/2)枚举分别是不放还是放到第一组还是放到第二组,并记录下来。
右边的3^(N/2)枚举后,再2^(N/2)看看左边符合这个值的那些,就行了。
总复杂度O(6^(N/2))。
其实调整左右大小可以使得复杂度更优。
来源:USACO 2012 OPEN GOLD subsets

题目 4179 毛一琛
2025-10-04 14:52:10