一道状压DP，单独记录一下解题过程。。。

其实最开始也不是很能看懂= =

感觉对于状压DP还是不太能做到举一反三，可能还没总结出规律吧

大致题意如下： 有一个 N * M 的棋盘，要求你将其分割为若干个1 * 2的长方形，问你有多少种分割方案。

有若干组数据

首先考虑到长方形的具体摆法，只有1 *2或者 2 * 1两种情况，这就意味着如果你确定了所有横向放置的长方形的位置，那么接下来纵向放置的长方形也就全部被确定了(因为他们只能将剩下的所有位置全部填充满，不会出现多种情况)

然而这个问题的情况依旧复杂，关键就在于找到一种合适的方法去不重不漏地遍历所有的情况，并加以统计。

基于长方形摆法的性质，我们可以尝试以列的方式进行动态规划，因为当我们考虑第i 列的时候，可以通过讨论第i - 1 列的合法情况是否可以通过将纵向放置的长方形转置为横向放置来实现下一步状态的转移。

那么，什么样的情况是合法的呢？很显然，纵向放置的长方形在同一列必须占据两格，也就意味着如果该状态出现奇数个空白格子就是不合法的。

所以我们先初始化所有的情况，将所有明显不合法的情况标记出来。

// 由于状态是否合法与n,m的具体量有关，所以每个样例都需要计算一次是否合法
for(int i = 0; i < 1<<n; i++){
            int cnt = 0; // 记录当前连续的0的个数
            bool valid = true; // 一开始认为其是合法的
            for(int j = 0; j < n; j++){
                if(i >> j & 1){ // 右移j位，也就是考察第j行的情况
                    if(cnt & 1){ // 如果第j行是1，并且在此之前有奇数个0位，那么这种情况就是不合法的
                        valid = false;
                        break;
                    }
                    cnt = 0; // 重置计数器，重新计算连续的0的个数
                }
                else cnt++; // 如果是0直接计数器加一
            }
            if(cnt & 1) valid = false; // 最后收尾判断一下末尾是否有奇数个0
            st[i] = valid; // 记录当时状态是否合法
}

也就是这一段在做的事情，具体解释可以参考注释。

当我们排除掉了一些明显不合法的情况，接下来就要考虑列与列的连接情况。

很显然对于连续的3列，我们不能存在有某一行含有三个1的情况(这样意味着它是一个 1 * 3的长方形)

所以接下来我们继续筛选掉不合法的情况，并将剩下的合法情况导入vector，在接着DP的时候，我们就只需要考虑vector中合法的情况就好了。

因为对于每一种状态的上一行来说可行的状态都是不同的，所以我们需要用一个队列数组来保存所有状态的所有合法情况。

vector<int> state[M];  // 统计最后可行的状态表示

具体代码如下:

        for(int i = 0; i < 1<<n; i++){
            state[i].clear(); // 因为有多组数组，所有要先清空上一个输出产生的可行方案
            for(int j = 0; j < 1<<n; j++){
                if((i&j) == 0 && st[i | j]){
                    // i & j == 0也就意味着二者不能有某一位相同，因为上一行已经是横着放了，无法继续延伸
                    // i | j 就是判断将i中横置的和j中横置的取并集，因为上一行横着放的，这一行横着放依旧是合法的(不视为延伸，而是新开一个横向的长方形)，而这一行横着放的可以是上一行中竖着放的情况转置过来
                    state[i].push_back(j);
                    // 第i个状态可以由第j个状态转移而来
                }
            }
        }

在最后我们的答案就是f[m + 1][0]中存的数，因为0意味着没有任何的长方形继续延伸，也就是合法的情况

完整代码如下:

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 12, M = 1 << N;
LL f[N][M];

bool st[M];
vector<int> state[M];  // 统计最后可行的状态表示

int n,m;

int main(){
    while(cin >> n >> m && (n || m)){
        for(int i = 0; i < 1<<n; i++){
            int cnt = 0;
            bool valid = true;
            for(int j = 0; j < n; j++){
                if(i >> j & 1){
                    if(cnt & 1){
                        valid = false;
                        break;
                    }
                    cnt = 0;
                }
                else cnt++;
            }
            if(cnt & 1) valid = false;
            st[i] = valid;
        }
        for(int i = 0; i < 1<<n; i++){
            state[i].clear();
            for(int j = 0; j < 1<<n; j++){
                if((i&j) == 0 && st[i | j]){
                    state[i].push_back(j);
                }
            }
        }
        memset(f, 0, sizeof f);
        f[0][0] = 1;
        for(int i = 1; i <= m; i++){
            for(int j = 0; j < 1<<n; j++){
                for( auto k : state[j]){
                    f[i][j] += f[i - 1][k];
                }
            }
        }
        printf("%lld\n", f[m][0]);
    }
}