蓝桥杯-回路计数（状态压缩、动态规划）-Toy模板网

这篇具有很好参考价值的文章主要介绍了蓝桥杯-回路计数（状态压缩、动态规划）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目描述

蓝桥学院由 $21$ 栋教学楼组成，教学楼编号 $11$ 到 $21$ 。对于两栋教学楼 $a$ 和 $b$ ，当 $a$ 和 $b$ 互质时， $a$ 和 $b$ 之间有一条走廊直接相连，两个方向皆可通行，否则没有直接连接的走廊。

小蓝现在在第一栋教学楼，他想要访问每栋教学楼正好一次，最终回到第一栋教学楼（即走一条哈密尔顿回路），请问他有多少种不同的访问方案？

两个访问方案不同是指存在某个 $i$ ，小蓝在两个访问方法中访问完教学楼 $i$ 后访问了不同的教学楼。

提示：建议使用计算机编程解决问题。

答案提交

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

运行限制

最大运行时间：1s
最大运行内存: 128M

思路和参考代码

本题可以使用动态规划的方法解决。

我们用 $1, 2, ..., 21$ 表示某1栋楼，设全集 $A = \{1,2,...,21\}$ 。设状态 $S_{V,\ l}$ 表示访问了子集 $V$ 中的全部路径（每个点均只访问1次）且最后一次落点在 $l$ 处的可行解的个数，其中 $\subseteq A$ ， $\in V$ 。即有动态规划方程
$S_{V,\ l} = \sum_{a\in V且a,l互质} S_{V- \{l\},\ a} \\S_{\{1\},\ 1 }= 1$

最终的答案为 $\sum_{i=2}^{21}{S_{A,\ i}}$ 。由于只有21栋楼，因此在实现时路径集合 $V$ 只需要使用位集压缩在1个int变量中，如经过了完整的21栋楼，经过的路径为0x1fffff。

完整实现如下：文章来源地址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();
    }
}