To boldly go where no one has gone before.

【学习笔记】状压dp

2019-01-31 11:31:39


例题在这里

状压dp就是用二进制数枚举每行的一种情况,然后用位运算的方式进行转移。会大量地运用按位与$(\&)$的运算。状压dp的数据范围特点是不超过12,因为只看朴素复杂度的话,$O(2^{12}{\times}2^{12}{\times}12)=O(10^8)$,而由于二层状态枚举是否进行取决于一层状态枚举是否被接受,所以复杂度可以降低到可接受范围。再往上的话可能会爆掉。

下面是P1879的代码。

#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$!!