2019牛客多校第五场E – independent set 1

题目链接:2019牛客多校第五场E

最多26个点,$2^n \approx 6 \times 10^7$,考虑用二进制压缩状态。状态$s$的第$i$位表示取或者不取第$i$个点。

我们用$f(s)$表示状态$s$的最大独立集的个数,可以从下面两个状态推得:

  • 二进制$s$的最后一个为1的位置不属于最大独立集$f(s) = f(s – {\rm lowbit}(s) )$
  • 二进制$s$的最后一个为1的位置属于最大独立集$f(s) = f(s – {\rm adj}(u)) + 1$

其中${\rm adj}(u)$表示最后一个为1的位置和它相邻节点的集合,即$v$在最大独立集中,则与它邻接的点一定不在最大独立集中。

二者取最大即可。时间复杂度$O(2^n)$。

需要特别注意这题空间卡得很紧,需要用char来存答案。

 

说点什么

avatar
50
  Subscribe  
提醒