状态压缩DP

状态压缩本质上就是用一个二进制数来表示出所有的状态，从而方便用位运算节省速度。

蒙德里安的梦想

要找到所有的方案数，我们需要找到所有横放1x2方格的合法方案数，当横放数量确定后，竖放的方格只需插入即可。

状态表示：用f[i] [j]记录第i列的状态j，其中状态j是用二进制表示的数，当前一位捅出来时为1，没捅出来为0。

f[i][j] = f[i - 1] [k]; //k表示能转化成j的所有合法方案。

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

typedef long long LL;

const int N = 12, M = 1 << N;

int n, m;
LL f[N][M];
vector<int> state[M];
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 ++ ){
                if (i >> j & 1){ // 当碰到一次1后判断之前遇见0的数量
                    if (cnt & 1){ // 为奇数则是不合法状态
                        is_valid = false;
                        break;
                    }
                    cnt = 0; //重新开始计算
                }
                else cnt ++ ;
            }
            if (cnt & 1) is_valid = false; // 末尾的0不会遇到1停止，最后再处理末尾的0
            st[i] = is_valid;
        }
        for (int i = 0; i < 1 << n; i ++ ){ // 插入所有能转化成j的状态k
            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];
            }
        }
        cout << f[m][0] << endl;
    }

    return 0;
}

最短Hamilton路径

同样，状态表示f[i] [j]指走到点j的状态i的路径，同样状态i用二进制数表示，

例如走0,1,2,4这三个点,则表示为:10111;
走0,2,3这三个点:1101;

状态转移方程

f[i][j]=min(f[i][j],f[i-(1<<j)][k]+w[k][j]);

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

const int N = 20, M = 1 << N;

int f[M][N], w[N][N];

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i ++ ){
        for (int j = 0; j < n; j ++ ){
            cin >> w[i][j];
        }
    }

    memset(f, 0x3f, sizeof f);
    f[1][0] = 0; // 初始化起点

    for (int i = 0; i < 1 << n; i ++ ){
        for (int j = 0; j < n; j ++ ){
            if (i >> j & 1) // 存在j
            for (int k = 0; k < n; k ++ ) // 走到j点之前，以k为终点的最短距离
                if (i >> k & 1) // 存在k
                f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
        }
    }
    cout << f[(1 << n) - 1][n - 1] << endl;
    return 0;
}