连通性状压DP

若将横着放的方格放置好，那么竖着放的方格如何放是固定的，即尽量塞满。

$ 时间复杂度O(M2^N2^N),空间复杂度O(2^NM)$
时间复杂度可以看成是指数级别的。

参考文献

算法基础课

AC代码

#include <iostream>
#include <cstring>
using namespace std;

typedef long long LL;
const int N = 12, M = 1 << N;

int n, m;
LL f[N][M];
bool st[M];//为j|k服务,即对于j|k的状态,0是连续的偶数个是否成立

int main(){
    while (cin >> n >> m, n || m){
        memset(f, 0, sizeof f);
        //初始化st数组
        for (int i = 0 ; i < 1 << n ; i ++){
            st[i] = true;
            int cnt = 0;//记录连续0的个数
            for (int j = 0 ; j < n ; j ++){
                if (i >> j & 1){
                    if (cnt & 1) st[i] = false;
                    cnt = 0;
                } else cnt ++;
            }
            if (cnt & 1) st[i] = false;
        }


        //状态压缩DP
        f[0][0] = 1;
        for (int i = 1 ; i <= m ; i ++){
            for (int j = 0 ; j < 1 << n ; j ++){
                for (int k = 0 ; k < 1 << n ; k ++){
                    if ((j & k) == 0 && st[j | k] )
                        f[i][j] += f[i - 1][k];
                }
            }
        }

        cout << f[m][0] << endl;
    }
    return 0;
}