算法学习笔记（48）——状态压缩DP

状态压缩DP

连通性问题

一、核心思想：

• 核心：先放横着的，再放竖着的
• 总方案数等于只放横着的小方块的合法方案数。
  • 如何判断当前方案是否合法？
  • 所有剩余位置，能否填充满竖着的小方块，需要是偶数个

二、方法：

化零为整 ==> 化整为零

• 状态表示（化零为整）：某一个状态表示某一类方案
  • f[i][j]表示已经将前i-1列摆好，且从第i-1列伸出到第i列的方案
    • 任何一个方块不会再摆到前i-1列内的任何一个位置
    • 从i-1列伸到i列的方案
• 状态计算（化整为零）：分割使得每一个部分可以被计算出来
  • 分割依据：最后一步操作
    • 第i-1列至第i列的情况已经固定(f[i][j])，从第i-2列至第i-1列的情况(f[i -1][k])没有固定，共有\(2^n\)种情况（每一行都有伸或不伸两种情况）
    • 针对这\(2^n\)种情况，判断能否构成合法方案
      1. j & k == 0 ：相邻三列内同一行不能两个小方块
      2. i-1列空着的位置能够填充竖着的小方块，即个数为偶数
    • 最终答案 f[m,0]，前m-1列摆好了，并且没有任何一个小方块伸到m列

三、优化

预处理合法状态：对每个状态j而言，有哪些状态k可以更新到j

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;

//M = 2 ^ N
const int N = 12, M = 1 << N;

int n, m;
LL f[N][M]; //状态转移方程
vector<int> state[M]; //存储所有合法状态
//判断某个状态是否合法，当前列空着的连续位置（0）是否为偶数
bool st[M]; 

int main() {
    while (cin >> n >> m, n || m) {
        //预处理
        for (int i = 0; i < 1 << n; i ++ ) {
            int cnt = 0; //表示0的个数
            bool is_valid = true; //表示是否合法
            for (int j = 0; j < n; j ++ ) //每行有n个数
                if (i >> j & 1) { //如果当前这一位是1
                    if (cnt & 1) { //有连续奇数个0
                        is_valid = false;
                        break;
                    }
                    // cnt = 0;
                }
                else cnt ++;
            //判断最后一个0
            if (cnt & 1) is_valid = false; 
            st[i] = is_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]) // i | j 为所有塞满的位置
                    state[i].push_back(j); //存入j到i的合法方案
        }

        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];

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

    return 0;
}