【学习笔记】状压dp

## 例题在[这里](https://www.luogu.org/problemnew/solution/P1879) 状压dp就是用二进制数枚举每行的一种情况，然后用位运算的方式进行转移。会大量地运用按位与$(\&)$的运算。状压dp的数据范围特点是不超过12，因为只看朴素复杂度的话，$O(2^{12}{\times}2^{12}{\times}12)=O(10^8)$，而由于二层状态枚举是否进行取决于一层状态枚举是否被接受，所以复杂度可以降低到可接受范围。再往上的话可能会爆掉。 下面是P1879的代码。 ```cpp #include<bits/stdc++.h> #define MAXN 13 using namespace std; const int MOD = 1e9; bool accept[1<<MAXN]; int F[MAXN]; int f[MAXN][1<<MAXN]; int m, n; int land[MAXN][MAXN]; int main() { memset(F, 0, sizeof(F)); memset(f, 0, sizeof(f)); memset(accept, 0, sizeof(accept)); cin >> m >> n; for(int i=0; i<(1<<n); i++) accept[i] = (!(i & (i<<1))) && (!(i & (i>>1))); for(int i=1; i<=m; i++) for(int j=1; j<=n; j++) { cin >> land[i][j]; F[i] = (F[i] << 1) + land[i][j]; } f[0][0] = 1; for(int i=1; i<=m; i++) for(int j=0; j<(1<<n); j++) { if(accept[j] && ((j & F[i]) == j)) //最坑！ for(int k=0; k<(1<<n); k++) if(!(j & k)) f[i][j] = (f[i-1][k] + f[i][j]) % MOD; } int ans = 0; for(int i=0; i<(1<<n); i++) ans = (ans + f[m][i]) % MOD; cout << ans; return 0; } ``` 其中$accept$维护的是发生转移的前提条件，比如这里的$accept$就是指没有连续的草地，也就是左移一位与自己按位与并上右移一位与自己按位与后的结果。如果连这个前提条件都不满足，那么枚举到的状态就是废的。 $F[i]$维护的是第$i$行土地的状态，也就是数据给出的状态。$f[i][j]$则表示在第$i$行的$j$状态下可能存在的方案总数，注意在开始的时候一定要把$f[0][0]$设为$1$，否则无论如何转移还是$0$。 而 $accept[j]$ $\&\&$ $((j$ $\&$ $F[i]) == j)$ 这句话则是最重要的，也是**最坑的**。 # 要记住的是：$==$的优先级不低于$\&$ 被坑了好几次才终于明白这个，真的是很难受啊。所以以后还是**勤打括号**，特别是不清楚优先级的时候，还是打括号靠谱一点，毕竟优先级这玩意儿调试也不太容易看出来。 同时，这句话的意思是枚举到的状态$j$不仅满足$accept$的条件，还能满足数据给出的条件。学会了按位与还可以这样用，**按位与上另一个数等于自己**，则表示对方为$0$的数位自己一定为$0$，这样就被框在$F[i]$的条件中了。 后面的二层枚举则更好理解了，枚举上一行的状态，如果满足题面的条件则发生转移。这里由于$k$已经被死死框在条件之内，也就是说所有不满足条件的$k$所对应的$f[i-1][k]$其实都是$0$，所以就算发生了错误的转移也没什么关系。因此$j$与$k$的关系只要满足题面意思就可以发生转移，所以让$j$和$k$按位与的结果为$0$即表示没有上下相邻的草地，然后发生状态转移。方程很简单就不写了。最后统计第$m$行的所有$f$之和，即答案。 感触： # 状压dp真暴力啊！ --- 2019/2/27更新 注意：枚举状态的时候一定要 ### 从$0$枚举到$(1<<n)-1$！！