蓝桥杯.回路计数(状压DP)

68 阅读 0 评论 45 点赞

我是靠谱客的博主害怕冬瓜，这篇文章主要介绍蓝桥杯.回路计数(状压DP)，现在分享给大家，希望可以做个参考。

Question:

Result：881012367360

21x21的图答案爆int也是够麻的

Solve:

图的遍历复杂度是21的阶乘，赛时不可能跑完，考虑DP

首先

21个点，用21位的二进制01串状压表示每一栋楼是否访问

所以现在的问题就转化成了

如何将一个含有1位1，20位0的二进制数变的21位都是1，这个就有点像19年的《糖果》了

DP的基本思路：

从初始状态开始，不断的去尝试下一个能到达的楼，并且将楼加入状态中（对应的楼的二进制位变为1），那么如果21位的二进制所有数都变为了1，就说明这是一种可行的路径，将这个路径计数到dp[ (1<<21) - 1][路径的末楼下标]

之后状态转移方程

dp[ i ][ j ]表示从状态 i 到 j 的路径数

dp[ i + (1 << k) ][ k ] += dp[ i ][ j ];

原状态 i 在楼 j 已经访问过的情况下去尝试将楼 k 加入已访问的点，如果可以，则新的状态会以k为终点，其路径数为原来的值加上dp[ i ][ j ]

某个楼x是否已经访问过的判断：

i >> x & 1 (状态 i 按位右移x位，之后取余) (判断状态 i 二进制数的第 x 位是否为1)

Code:

复制代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool v[25][25]; 
ll dp[1<<21][25];
inline int gcd(int a, int b){
	return b==0 ? a : gcd(b, a%b);
}
int main(void)
{
	ll res = 0;
	//存边,注意下标 
	for(int i = 1;i <= 21; i++){
		for(int j = 1; j <= 21; j++){
		if(gcd(i, j) == 1) 
			v[i-1][j-1] = v[j-1][i-1] = true;
		else
			v[i-1][j-1] = v[j-1][i-1] = false;
	}
	}
	dp[1][0] = 1;
	for(int i = 1; i < (1<<21); i++){
	for(int j = 0; j < 21; j++){
		
		//如果当前状态中不存在楼j，跳过 
		if(!(i>>j&1)) continue;
		            
		//寻找从楼j能够到达的下一栋楼
		for(int k = 0; k < 21; k++){
			
			//楼k已经访问或者j到k无边，跳过 
			if((i>>k&1) || !v[j][k]) continue;
			
			dp[i+(1<<k)][k] += dp[i][j];
		}
	}
	}
	
	//将以i为结尾点的回路求和 
	for(int i = 0; i < 21; i++) 
		res += dp[(1<<21)-1][i];
	cout <<res;
	return 0;
}