状压DP

蒙德里安的梦想

求把 N ∗ M N*M NM的棋盘分割成若干个1*2的的长方形,有多少种方案。

先考虑横着放的情况 竖着放的自然唯一确定

状态表示

f [ i ] [ j ] f[i][j] f[i][j]表示第 i i i列的每一行小方格被占用的情况 j j j为二进制数 1 1 1表示占用

状态计算

j j j表示 i i i列的状态 k k k表示 i − 1 i - 1 i1列的状态

能从 i − 1 i-1 i1列转移到 i i i列的条件

① 两列没有冲突的情况 j & k = = 0 j \& k == 0 j&k==0

②第 i − 1 i-1 i1列所有连续的空白格为偶数 j ∣ k j | k jk不存在连续奇数个 0 0 0

f [ i ] [ j ] + = f [ i − 1 ] [ k ] f[i][j] += f[i-1][k] f[i][j]+=f[i1][k]

时间复杂度 O ( N ∗ 2 N ∗ 2 N ) O(N * 2 ^ {N} * 2^{N}) O(N2N2N)

const int N = 12, M = 1 << N;
LL f[N][M];
bool st[M];
int n, m;

int main() {
   
	while (cin >> n >> m, n || m) {
   
		memset(f, 0, sizeof f);
		for (int i = 0;i < 1 << n;++i) {
   //枚举1到n的每一个二进制数
			st[i] = true;//假设成立
			int cnt = 0;//当前这一段连续0的个数
			for (int j = 0; j < n;++j) {
   
				if ((i >> j) & 1) {
   //如果第j位为1 说明上一段连续的0已经结束
					if (cnt & 1)st[i] = false; // 如果为奇数 不成立
					cnt = 0; // 重置cnt
				}
				else cnt++;
			}
			if (cnt & 1)st[i] = false; //判断最后一段是否合法
		}


		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;;//所有第m列没有方格出来的方案数即为答案
	}
	return 0;
}

最短Hamilton路径

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

状态表示

f [ i ] [ j ] f[i][j] f[i][j]表示从0走到 j j j,走过的所有点是 i i i的所有路径 i i i为二进制数 0010001110... 0010001110... 0010001110...

### 状态计算

f [ i ] [ j ] f[i][j] f[i][j] = m i n ( f [ i ] [ j ] , f [ i − ( 1 < < j ) ] [ k ] + m p [ k ] [ j ] ) min(f[i][j], f[i - (1 << j)][k] + mp[k][j]) min(f[i][j],f[i(1<<j)][k]+mp[k][j]) 倒数第二个点为k的状态

const int N = 21, M = 1 << N;
int f[M][N];
int mp[N][N];

int main() {
   
	int n;cin >> n;
	for (int i = 0; i < n;++i) {
    //读入图
		for (int j = 0; j < n;++j) {
   
			cin >> mp[i][j];
		}
	}

	memset(f, 0x3f, sizeof f);
	f[1][0] = 0; // 只经过一个点时 距离为0
	for (int i = 0;i < 1 << n;++i) {
    //状态为i
		for (int j = 0; j < n;++j) {
    // 以j为终点
			if (i >> j & 1)//经过了j这一点的状态才有意义
				for (int k = 0; k < n;++k) //枚举从哪一个点转移过来
					if (i - (1 << j) >> k & 1) //没有经过j并且终点为k
						f[i][j] = min(f[i][j], f[i - (1 << j)][k] + mp[k]     [j]);
		}
	}
	cout << f[(1 << n) - 1][n - 1] << endl; //每一个点都经过 且终点为n-1

	return 0;
}