状态压缩

· · 个人记录

定义 DP 状态的时候，有时不好表示，那么可以直接状压。

基本适用于：n\le 20

具体地，dp_i 的 i 表示一整行的状态。

比如 i=14，转化为 2进制 得 1110。表示此行第 1~3 列状态为 true，第 4 列状态为 False。

单行的时空为 O(2^n)，但是通常是 dp_{i,j} 表示第 i 行状态为 j 的数量，根据 i-1 行进行状态转移。所以设 n 行 m 列，则时空为 O(n·2^m)。

for(int i = 1;i <= n; ++i) 
    for(int j = 0;j < (1 << n); ++j)
        if(j 符合条件)
        for(int k = 0;k < (1 << n); ++k) // 前一个状态
            if(j and k 符合条件)
                转移

给出一些技巧：

二进制下，如果保证相邻数位不都为 1，可写成 !(j & (j >> 1)）and !(j & (j << 1))。