题目描述
蓝桥学院由 21 21 21 栋教学楼组成,教学楼编号 11 11 11 到 21 21 21。对于两栋教学楼 a a a和 b b b,当 a a a和 b b b互质时, a a a和 b b b之间有一条走廊直接相连,两个方向皆可通行,否则没有直接连接的走廊。
小蓝现在在第一栋教学楼,他想要访问每栋教学楼正好一次,最终回到第一栋教学楼(即走一条哈密尔顿回路),请问他有多少种不同的访问方案?
两个访问方案不同是指存在某个 i i i,小蓝在两个访问方法中访问完教学楼 i i i后访问了不同的教学楼。
提示:建议使用计算机编程解决问题。
答案提交
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。
运行限制
最大运行时间:1s
最大运行内存: 128M
思路和参考代码
本题可以使用动态规划的方法解决。
我们用
1
,
2
,
.
.
.
,
21
1,2,...,21
1,2,...,21表示某1栋楼,设全集
A
=
{
1
,
2
,
.
.
.
,
21
}
A = \{1,2,...,21\}
A={1,2,...,21}。设状态
S
V
,
l
S_{V,\ l}
SV, l表示访问了子集
V
V
V中的全部路径(每个点均只访问1次)且最后一次落点在
l
l
l处的可行解的个数,其中
V
⊆
A
V \subseteq A
V⊆A,
l
∈
V
l \in V
l∈V。即有动态规划方程
S
V
,
l
=
∑
a
∈
V
且
a
,
l
互质
S
V
−
{
l
}
,
a
S
{
1
}
,
1
=
1
S_{V,\ l} = \sum_{a\in V且a,l互质} S_{V- \{l\},\ a} \\S_{\{1\},\ 1 }= 1
SV, l=a∈V且a,l互质∑SV−{l}, aS{1}, 1=1
最终的答案为
∑
i
=
2
21
S
A
,
i
\sum_{i=2}^{21}{S_{A,\ i}}
∑i=221SA, i。由于只有21栋楼,因此在实现时路径集合
V
V
V只需要使用位集压缩在1个int
变量中,如经过了完整的21栋楼,经过的路径为0x1fffff
。文章来源:https://www.toymoban.com/news/detail-472809.html
完整实现如下:文章来源地址https://www.toymoban.com/news/detail-472809.html
public class Main {
static boolean[][] isConnected = new boolean[22][22];
static final int MAXN = 0x1fffff;
static long[][] counts = new long[MAXN + 1][22];
static void init() {
for (int i = 1; i <= 21; i++) {
for (int j = i + 1; j <= 21; j++) {
boolean flag = false;
for (int k = 2; k <= i; k++) {
if (i % k == 0 && j % k == 0) {
flag = true;
break;
}
}
if (!flag) {
isConnected[i][j] = isConnected[j][i] = true;
}
}
}
}
static void debug() {
for (int i = 1; i <= 21; i++) {
for (int j = i + 1; j <= 21; j++) {
if (isConnected[i][j])
System.out.printf("%d %d\n", i, j);
}
}
}
static void dp() {
counts[1][1] = 1;
for (int i = 1; i <= MAXN; i++) {
for (int j = 1; j <= 21; j++) {
if (((i >> (j - 1)) & 1) == 0)
continue;
for (int k = 1; k <= 21; k++) {
if (((1 << (k - 1)) & i) != 0 || !isConnected[j][k])
continue;
counts[i | (1 << (k - 1))][k] += counts[i][j];
}
}
}
}
static void printAnswer() {
long cnt = 0;
for (int i = 1; i <= 21; i++) {
if (isConnected[i][1])
cnt += counts[MAXN][i];
}
System.out.println(cnt);
}
public static void main(String[] args) {
init();
// debug();
dp();
printAnswer();
}
}
到了这里,关于蓝桥杯-回路计数(状态压缩、动态规划)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!