熟练掌握动态规划——《挑战程序设计竞赛》

发表于 | 分类于 | 浏览次数
字数统计: 1,388 字 | 阅读时长 ≈ 6 分钟

3.4.1 状态压缩DP

可能在一些DP的递推关系式中，下表不是普通的整数，但是我们可以把它编码成一个整数，或者给它们定义一个全序关系并用二叉搜索树存储，从而可以记忆化搜索来求解。

旅行商问题：
给定一个n个顶点组成的带权有向图的距离矩阵d(I,j)（INF表示没有边）。要求从顶点0出发，经过每个顶点恰好一次后再回到顶点0。问所经过的边的总权值的最小值是多少？
$2\le n \le 15$
$0\le d(i,j) \le 1000$

所有可能的路线共有(n-1)!种，就算此题的n很小也不能列举。

假设现在已经访问过的顶点的集合（起点0当作还未访问过的顶点）为S，当前所在的顶点为v，用dp[s][v]表示从v出发访问剩余所有顶点最终返回顶点0这一段路径的权值总和的最小值，则有如下的递推关系式：

这个递归式中，S是一个集合而不是普通的整数，对于集合我们可以把每一个元素的选取与否对应到一个二进制位里，从而把状态压缩到一个整数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//输入
#define INF 0x3f3f3f3f
int n;
int d[MAX_N][MAX_N];
int dp[1<<MAX_N][MAX_N];
int rec(int S,int v)
{
	if(dp[S][v] >= 0)
	{
		return dp[S][v];
	}
	if(S==(1<<n)-1 && v==0)//已经访问过所有节点并回到0号点，所以剩余的权值为0
	{
		return dp[S][v] = 0;
	}
	int res = INF;
	for(int u=0;u<n;u++)
	{
		if(!(S>>u & 1))
		{
			res = min(res,rec(S|1<<u,u)+d[v][u]);
		}
	}
	return dp[S][v] = res;
}

void solve()
{
	memset(dp,-1,sizeof(dp));
	printf("%d\n",rec(0,0));
}

另外可以不用递归而从全序排列字典序倒叙来循环求解。而像这样针对集合的DP我们一般叫状态压缩DP。

铺砖问题
给定$n\times m$的格子，每个格子被染成了黑色或者白色。现在要用$1\times 2$的砖块覆盖这些格子，要求块与块之间不互相重叠，且覆盖了所有白色的格子，但不覆盖任意一个黑色格子。求一共有多少种覆盖方法，输出方案数对M取余后的结果。

这道题的想法有点难理解昂。

索性不强行理解了，咱们根据代码来理解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<iostream>
using namespace std;
bool M[17][17]; //存初始化格子的颜色
/*
dp[used]:=(这个used是第二个参数，m个格子的枚举)从起始位置到当前的m个格子，都被覆盖的所有可能性
*/
int dp[2][1<<15]; 

int main(){
	int n,m,mod;
	while(cin>>n>>m &&n&&m){
		cin>>mod;
		memset(dp,0,sizeof(dp));
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){ //从0开始后面会好操作一点 
				char input; cin>>input;
				if(input=='.') M[i][j]=0; //0:白 1：黑，将0全变为1 
				else M[i][j]=1;
			}
		}
		int *now=dp[0],*nex=dp[1];
		now[0]=1;
		for(int i=n-1;i>=0;i--){ //从n-1 开始会方便二进制表示状态，我也不知道为什么就方便起来了
			for(int j=m-1;j>=0;j--){
				for(int used=0;used< (1<<m) ;used++){ //遍历状态,这里反过来表示  
/*
为什么要遍历呢？看下面竖着放的代码有一个： res+=now[used|1<<j];
横着放也是一样，是从当前used的状态中新置1一个比特，因此需要！
*/
					if(used>>j & 1 || M[i][j]){ //假如这个位置被用了或者是1 不用填 就是不需要被覆盖呢，那么下一个处理的格子的可能性就等于这一个格子的可能性，这个格子的可能性也就对于这个格子没被覆盖的可能性，毕竟要递推过来的嘛。
						nex[used]=now[used & ~(1<<j)];  //把第j这个位置上的比特置为0，也就是这个格子没被覆盖的意思
					} 
					else{
						int res=0;
/*
对于一个白色格子，那么覆盖它的可能性就等于横放的可能性（右边和它一起被覆盖）+竖放可能性（下边和它一起被覆盖）。
*/
						if(j+1<m && !(used>>(j+1)&1) && !M[i][j+1]){ //横着放 
/*
j+1的原因是上面for循环是j--，   <- 这个方向遍历的；
这个if的!(used>>(j+1)&1) 条件是说j+1这个位置，也就是右边这个格子，在当前枚举的这种状态下没有被覆盖，因为只有右边这个格子没被覆盖，这下横着放，占了右边格子和当前格子才行，那为什么不能是j-1呢？因为j-1还没处理到，我的理解是不能影响后面还未处理的格子。那么这种可能性就等于右边和它一起被覆盖的可能性。
*/
							res+=now[used|1<<(j+1)];
						}
						if(i+1<n && !M[i+1][j] ){ //竖着放， 同理了，那么这种可能性就等于下边的格子和它一起被覆盖的可能性。
							res+=now[used|1<<j];
						}
						nex[used]=res%mod;
					} 
					
				}
				swap(now,nex);
			}
		}
		cout<<now[0]<<endl;
	}
	return 0; 
}
/*
3 3 100
. . .
. X .
. . .
*/