前言

本文主要总结状压 dp 有关的内容

前置芝士

枚举子集

若有一个集合，我们可以通过枚举每个元素选或不选来实现集合中子集的枚举。

其中，可以用二进制来存储每个元素选或不选的状态。$0$ 不选，$1$ 选。

所以我们枚举集合中的所有子集即可以这样写($n$ 为集合中元素数量)：

for(int s = 0 ; s < (1 << n) ; s ++){
  //code
}

位运算

位运算是指定义在二进制上的运算

• 与运算 $\&$ 都为 $1$ 则为 $1$，否则为 $0$
• 或运算 $\text{|}$ 都为 $0$ 则为 $0$，否则为 $1$
• 异或运算 ^ 相同为 $1$ 不同为 $0$
• 右移位 << 数向右移 $k$ 位，相当于 $\times 2^k$
• 左移位 >> 数向左移 $k$ 位，相当于 $/2^k$

其应用如下：

• 取 $S$ 第 $i$ 位： (S >> i) & 1
• 将 $S$ 第 $i$ 位变为 $0$： S & ~(1 << i)
• 将 $S$ 第 $i$ 位变为 $1$： S | (1 << i)
• 将 $S$ 第 $i$ 位取反： S ^ (1 << i)

状压 dp

状压 dp 是以状态压缩思想为核心的 dp。其中 dp 的状态有一维就是用二进制压缩来表示元素的状态。具体看后文例题

列题

P10447 最短 Hamilton 路径

solution

用状压 dp 解决，因为只有用状压 dp 才知道当前走了哪些点

设 $dp_{S , i}$ 表示目前在点 $i$，所有点到达的状态为 $S$ 的最短 Hamilton 路径。

因为点 $i$ 可以由任意点转移而来，所以有如下转移：

$$\begin{split} dp_{S,i} &= \min(dp_{S,i} , dp_{S',j} + dis(i,j)) \\ S' &= S - \{i\} \end{split}$$

显然地，根据状态表示，有两个限制条件：

• $i \neq j$
• $i \in S \& j \in S'$

初始状态 $dp_{1,0} = 0$

最后的答案就是 $dp_{S,n - 1}$ 其中 $S$ 集合都为 $1$

code

	memset(dp , 0x3f3f3f3f , sizeof dp);
	dp[1][0] = 0;
	
	for(int i = 1 ; i < (1 << n) ; i ++){
		for(int j = 0 ; j < n ; j ++){
			if(!(i >> j) & 1) continue;
			for(int k = 0 ; k < n ; k ++){
				if(((i ^ (1 << j)) >> k) & 1){
					dp[i][j] = min(dp[i][j] , dp[i ^ (1 << j)][k] + dis[j][k]);
				}
			}
		}
	}
	cout << dp[(1 << n) - 1][n - 1];

P10975 Mondriaan's Dream

题意：求用 $1\times2$ 的小矩形铺满 $h\times w$ 的大矩形有多少种方式。小矩形可以横着放和竖着放

solution

首先可以构造出一种朴素的铺大矩形的方式：即先竖着放置矩形，放完之后再横着放置矩形，看大矩形能否被铺满

显然的，我们可以竖着一行一行的放置矩形，这样可以满足 $dp$ 的无后效性。只考虑当前行与上一行的状态，可以设 $dp_{S,i}$ 表示放置到当前第 $i$ 行的状态为 $S$，有多少种可能方案。其中 $S$ 中的元素为 $1$ 表示上一行有竖着放置的矩形伸到了当前行中；为 $0$ 表示当前方格用于放置横着的矩形

有了状态便容易得出转移为：

$$dp_{S,i} = \sum{dp_{S',i-1}}$$

其中 $S$ 和 $S'$ 要满足以下条件：

• $S$ 与 $S'$ 中每个全为 $0$ 的段的长度为偶数 ，这是因为状态中 $0$ 用于放置横着的矩形，所以长度要为 $2$ 的倍数才能放横着的矩形
• $S$ 和 $S'$ 按位与结果为 $0$，也就是在相同位置 $S$ 和 $S'$ 最多有一个 $1$。因为上一行方格如果被伸入，则当前行方格不可能被深入

可以画个图想一想

初始状态 $dp_{0,0} = 1$，表示初始时什么都没有用 $1$ 种方案

最后的答案就是 $dp_{0,h}$ 前 $h - 1$ 行都处理完了，且没有伸入的。也就是整个大矩形被铺满

code

bool check(int s){
	int cnt = 0;
	
	for(int i = 0 ; i < w ; i ++){
		if((s >> i) & 1){
			if(cnt % 2 != 0) return false;
			cnt = 0;
		}
		else cnt ++;
	}
	return (cnt % 2 == 0);
}

void solve(){
	while (cin >> h >> w && (h || w)) {
		if(h < w) swap(h , w);
		
		for(int i = 0 ; i <= (1 << w) ; i ++){
			vis[i] = check(i);
		}
		memset(dp , 0 , sizeof dp);
		dp[0][0] = 1;

		for (int i = 1 ; i <= h ; i ++) {
			for (int s = 0 ; s < (1 << w) ; s ++) {
				for (int k = 0 ; k < (1 << w) ; k ++) {
					if (!vis[s | k] || (s & k)) continue;
					dp[i][s] += dp[i - 1][k];
				}
			}
		}
		cout << dp[h][0] << endl;
	}
}