loj2540 「PKUWC2018」随机算法 【状压dp】题目链接题解
题目链接loj2540题解有一个朴素三进制状压\(dp\)，考虑当前点三种状态：没考虑过，被选入集合，被排除就有了\(O(n3^{n})\)的转移但这样不优，我们考虑优化状态设\(f[i][S]\)表示独立集大小为\(i\)，不可选集合为\(S\)【要么是已经在独立集中，要么已经被排除了】那么剩余点都是可选的就枚举剩余点\(u\)，记\(u\)相邻的集合为\(S_u\)，那么当\(...
