开始补 dp 了。
状压 dp
常见套路：数据范围小，能将状态用 \(0/1\) 表示，且状态的表示一般有所限制（例如不能将两个 \(1\) 放在一起）。
若设当前行状态为 \(S\)，则 \((S<<1)\&S\) 和 \((S>>1)\&S\) 能把出现相邻 \(1\) 的状态舍去，间隔同理。
若题目支持 \(3^n\) 做法，可以考虑枚举所有子集 for(int G = S; G; G = (G - 1) & S) 用子集来转移。
一般状压题目可以先预处理出第一行的状态与答案，然后再转移。
遇到选价值的题目，顺推能处理出所选的数的价值总和， a[S] = a[S ^ (S & (-S))] + a[S & (-S)] 。
若需要枚举子集，且子集推到当前集合只需添加一个状态，可以用 \(\text{lowbit}\) 每次取出最高位后异或操作转移 for(int G = S, Sl; G; G ^= Sl) Sl = G & (-G), dp[S]+=dp[G ^ Sl]; 。