动态规划：状态压缩 (蒙德里安的梦想、最短Hamilton路径)

状态压缩DP

AcWing 291.蒙德里安的梦想

求把 \(N* M\) 的棋盘分割成若干个 \(1*2\) 的的长方形，有多少种方案。 例如当 \(N=2，M=4\) 时，共有\(5\) 种方案。当 \(N=2，M=3\) 时，共有3种方案。 如下图所示：

输入格式
输入包含多组测试用例。 每组测试用例占一行，包含两个整数 \(N\) 和 \(M\)。 当输入用例 \(N=0，M=0\)时，表示输入终止，且该用例无需处理。

输出格式
每个测试用例输出一个结果，每个结果占一行。

数据范围
\(1≤N,M≤11\)

输入样例：

1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0

输出样例：

1
0
1
2
3
5
144
51205

Code：
\(f[i][j]\)表示第i列按状态 \(j\) 摆放时，从 \(i-1\) 列(状态 \(k\) )转移过来的方案数
第二维的状态中 \(0\) 表示竖着放，\(1\) 表示横着放
第 \(i-1\) 列状态是否能转移到第 \(i\) 列的条件：
①第 \(i\) 列状态 \(j\) 和第 \(i-1\) 列状态 \(k\) 不能冲突 \((j \& k) == 0\)；
②第 \(i\) 列状态 \(j\) 确定后，第 \(i-1\) 列状态k的连续空白格子的长度必须是偶数
\(st[ j | k] = true\).

初始状态: \(f[0][0] = 1\), 其余全为 \(0\);第 \(0\) 列只能是全 \(0\) 的状态
最终状态: \(f[m][0]\) , 棋盘有 \(0 \sim (m-1)\) 列，但后面一列会影响前一列，多出的一列必须是全0.

#pragma once
#include 
#include 

using namespace std;

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

long long f[N][M];
/*
f[i][j]表示第i列按状态j摆放时，从i-1列(状态k)转移过来的方案数
第二维的状态中0表示竖着放，1表示横着放
第i-1列状态是否能转移到第i列的条件：
①第i列状态j和第i-1列状态k不能冲突 (j & k) == 0；
②第i列状态j确定后，第i-1列状态k的连续空白格子的长度必须是偶数 st[ j | k] = true.

初始状态:f[0][0] = 1, 其余全为0;第0列只能是全0的状态
最终状态:f[m][0], 棋盘有0~(m-1)列，但后面一列会影响前一列，多出的一列必须是全0.
*/

bool st[M]; // 判断是否存在连续的偶数个0

void modriann_dream()
{
	int n, m;
	// 输入n, m, 当n和m不同时为零的时候, 都可以进入
	while (cin >> n >> m, n || m)
	{
		for (int i = 0; i < 1 << n; ++i)
		{
			int cnt = 0; //开始连续的零的个数为0个
			st[i] = true; // 假设第i为为true，表示存在连续的偶数个零
			for (int j = 0; j < n; ++j)
				if (i >> j & 1) //去除的数i第j为数字为1
				{
					if (cnt & 1) // 如果cnt为奇数，不满足转移条件
						st[i] = false;
					cnt = 0;
				}
				else cnt++;

			if (cnt & 1) st[i] = false; //判断最后一段连续的零是否是偶数个
		}

		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 (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; // 最后的答案是最后一列的前一列伸出来的小方块数量为0
	}
}

AcWing 91. 最短Hamilton路径

给定一张 \(n\) 个点的带权无向图，点从 \(0\sim n-1\) 标号，求起点 \(0\) 到终点 \(n-1\) 的最短Hamilton路径。 Hamilton路径的定义是从 \(0\) 到 \(n-1\) 不重不漏地经过每个点恰好一次。

输入格式
第一行输入整数n。 接下来n行每行n个整数，其中第 i 行第 j 个整数表示点 i 到 j 的距离（记为a[i,j]）。 对于任意的x,y,z，数据保证 a[x,x]=0，a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]>=a[x,z]。

输出格式
输出一个整数，表示最短Hamilton路径的长度。

数据范围
\(1≤n≤20 0≤a[i,j]≤10^7\)

输入样例：

5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0

输出样例：

18

Code:
\(f[i, j]\)表示从起点 \(0\) 到第 \(j\) 点，经过点为 \(i\) 的所有路径的距离最小值。 \(i\) 表示二进制压缩状态，存储经过哪些节点的信息， \(j\) 表示从第 \(0\) 点走到第 \(j\) 点。
初始状态为 \(f[0][j] = +\infty， f[1][0] = 0\);
最终问题解为 \(f[“11…1”, n - 1]\)
即 \(f[2^n-1][n -1]\).
状态转移：将压缩状态为 \(i\) 的路径 \(0 \sim j\) 分为 \(0→k\) (不包括 \(k\) )和 \(k→j\)。 \(f[i][j] = min(f[[i - (1 << j)][k] +w[k][j]); (\ "i - (1 << j)"确保该状态第j位为0，不经过j)\)

#include 
#include 
#include 

using namespace std;

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

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

int main()
{
    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; //表示从第一个点到第一个点得距离是0
    
    for (int i = 1; i < 1 << n; ++i) // i=1,表示从第一个点开始，i得每一位是1代表一个状态
        for (int j = 0; j < n; ++j) // 遍历所有得点
            if (i >> j & 1) // 到第j个点是不是可行得
                for (int k = 0; k < n; ++k) // 可行得话，看看它得上一个点k是谁
                    if (i >> k & 1) // 确保i能走到第k个点，k可以到j
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]); //比较所有可行得第k个点，选出来最小得距离
                        
    cout << f[(1 << n) - 1][n - 1] << endl; //最终得答案是走过所有得n个点，然后到达第n个点，也就是j = n - 1
    return 0;
}