概述
文章目录
- 前言
- 一、题目
- 二、思路
- 1.状态
- 2.上一个状态以及转移方程
- 3.填表
- 4.代码:
- 总结
前言
又是自闭的一天
一、题目
问题描述
蓝桥学院由 21 栋教学楼组成,教学楼编号 1 到 21。对于两栋教学楼 a 和 b,当 a 和 b 互质时,a 和 b 之间有一条走廊直接相连,两个方向皆可通行,否则没有直接连接的走廊。小蓝现在在第一栋教学楼,他想要访问每栋教学楼正好一次,最终回到第一栋教学楼(即走一条哈密尔顿回路),请问他有多少种不同的访问方案?两个访问方案不同是指存在某个 i,小蓝在两个访问方法中访问完教学楼 i 后访问了不同的教学楼。
答案:881012367360
二、思路
状压DP。设状态由长度为 21 21 21的 01 01 01串构成,左起第 i i i个数字表示 i i i是否走到过。如 0110 0110 0110表示 1 1 1, 4 4 4没有走到过。
1.状态
设 d p [ i ] [ s ] dp[i][s] dp[i][s]表示,从1走到 i i i,状态为 s s s的方案数。
2.上一个状态以及转移方程
对于
d
p
[
i
]
[
s
]
dp[i][s]
dp[i][s],考虑从哪些状态可以转移到
(
i
,
s
)
(i,s)
(i,s)?
是从节点
i
i
i的一个邻接点转移过来的。设他的邻接点为
t
a
r
tar
tar,则有:
d
p
[
i
]
[
s
]
=
d
p
[
t
a
r
]
[
s
p
r
e
]
dp[i][s]=dp[tar][s_{pre}]
dp[i][s]=dp[tar][spre],其中s_{pre}是s的上一个情况。
当然
i
i
i不止一个临界点,所以应该是所有邻接点的
d
p
dp
dp值求和。
d
p
[
i
]
[
s
]
=
Σ
d
p
[
t
a
r
]
[
s
p
r
e
]
dp[i][s]=Σdp[tar][s_{pre}]
dp[i][s]=Σdp[tar][spre]
3.填表
方程得到之后,剩下的就是一个填表问题。(DFS递不动了,不知道为啥跑一百年跑不出来)
可以发现应该是从小到大
(
1000...000
1111...111
)
(1000...000~1111...111)
(1000...000 1111...111)枚举状态(
s
s
s),对于每个
s
s
s计算
d
p
[
i
]
[
s
]
dp[i][s]
dp[i][s],
i
∈
[
1
,
21
]
i∈[1,21]
i∈[1,21]。
从小推大。
可以自行填一个N=3的表理解一下,循环顺序不能错。
4.代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=21;
int edge[27][27];
const int maxn=1<<22;
ll dp[27][maxn];//dp i j 1-->i 状态为j的方案书
ll vis[maxn];
//第i位变1 S& 1<<21-i;
//第i位变0 S& ~[1<<21-i];
//all 1 (1<<N)-1
// 1000000000——1<<(N-1)
//取第i位 s>>(N-tar)&1
const ll las=(1<<N)-1;
const ll fir=1<<(N-1);
ll all_1=(1<<N)-1;
int main(){
int i,j;
for(i=1;i<=N;i++){
for(j=i+1;j<=N;j++){
if(__gcd(i,j)==1){
edge[i][j]=1;
edge[j][i]=1;
}
}
}
dp[1][1<<(N-1)]=1;
for(int state=fir;state<=las;state++){
for(i=1;i<=N;i++)
{
//cout<<"枚举状态"<<state<<endl;
//state要有i,即第i位为1
int i_bit=state>>(N-i)&1;
if(i_bit!=1){
//cout<<"没有"<<i<<endl;
continue;
}
int tar;
int pre_state=state;
//pre_state第i位变0
pre_state=pre_state&(~(1<<(N-i)));
//cout<<"pre_state="<<pre_state<<endl;
for(tar=1;tar<=N;tar++){
//cout<<"tar="<<tar<<endl;
int tar_bit_pre=pre_state>>(N-tar)&1;//取pre_state第tar位
if(edge[tar][i]==1&&tar_bit_pre==1){//是邻接点且pre_state第tar位为1
dp[i][state]+=dp[tar][pre_state];
//cout<<"更新辣 add"<<dp[tar][pre_state]<<endl;
}
else if(edge[tar][i]==0){
//cout<<"没有这个邻接点n";
}
else if(tar_bit_pre==0){
//cout<<"pre_state中没有"<<tar<<endl;
}
}
}
}
ll ans=0;
for(i=1;i<=N;i++){
ans+=dp[i][all_1];//ALL 1
}
cout<<ans<<endl;
return 0;
}
总结
提示:这里对文章进行总结:
例如:以上就是今天要讲的内容,本文仅仅简单介绍了pandas的使用,而pandas提供了大量能使我们快速便捷地处理数据的函数和方法。
最后
以上就是风趣黑夜为你收集整理的蓝桥杯练习——回路计数前言一、题目二、思路总结的全部内容,希望文章能够帮你解决蓝桥杯练习——回路计数前言一、题目二、思路总结所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复