【DFS, 动态规划】垒骰子【蓝桥杯】

题目

试题历届真题垒骰子【第六届】【省赛】【C组】

1217. 垒骰子

赌圣 atm 晚年迷恋上了垒骰子，就是把骰子一个垒在另一个上边，不能歪歪扭扭，要垒成方柱体。

经过长期观察，atm 发现了稳定骰子的奥秘：有些数字的面贴着会互相排斥！

我们先来规范一下骰子： $1$ 的对面是 $4$ ， $2$ 的对面是 $5$ ， $3$ 的对面是 $6$ 。

假设有 $m$ 组互斥现象，每组中的那两个数字的面紧贴在一起，骰子就不能稳定的垒起来。

atm 想计算一下有多少种不同的可能的垒骰子方式。

两种垒骰子方式相同，当且仅当这两种方式中对应高度的骰子的对应数字的朝向都相同。

由于方案数可能过多，请输出模 $10^9 + 7$ 的结果。

输入格式

第一行包含两个整数 $n,m$ ，分别表示骰子的数目和排斥的组数。

接下来 $m$ 行，每行两个整数 $a,b$ ，表示 $a$ 和 $b$ 数字不能紧贴在一起。

输出格式

共一个数，表示答案模 $10^9 + 7$ 的结果。

数据范围

对于 30% 的数据： $n \le 5$
对于 60% 的数据： $n \le 100$
对于 100% 的数据： $0 < n \le 10^9, m \le 36$

输入样例：

2 1
1 2

输出样例：

解题

方法一：DFS(超时)

思路

每个骰子有 $6$ 个面，而在上下面固定时可以旋转 $4$ 次，那么如果 $n$ 个骰子垒在一起不存在冲突面时就有 $6^n \times 4^n$ 种情况。

以测试用例：

2 1
1 2

为例，其表示有 $2$ 个骰子垒在一起，其中有一组排斥面： $1$ 与 $2$ 互相排斥。
那么：

当第二个骰子 $4$ 朝上时，其 $1$ 朝下，第一个骰子就不能把 $2$ 朝上，少了一种情况。
当第二个骰子 $5$ 朝上时，其 $2$ 朝下，第一个骰子就不能把 $1$ 朝上，又少了一种情况。

所以此时垒骰子的方案数是： $(6^2 - 1 - 1) \times 4^2 = 34 * 16 = 544$ ，如图(没体现出四周旋转多形成的方案)：

那么很容易想到使用递归模拟求解：
用一个哈希表(opp)(可用数组代替)定义骰子的对面：opp[1] = 4， opp[4] = 1, opp[2] = 5, ...。
再用一个哈希表(conflict)(可用数组代替)记录骰子的对立面。

从最上层的骰子(n)开始递归：

递归函数 dfs(int top, int dice)，其中 top 表示当前骰子朝上的数字，dice 表示当前骰子在第几层。
递归的结束条件：当递归到第一层骰子时结束，返回该骰子可以有 $4$ 种摆放方案(侧面的四个方向)。
对于 n~2 层的骰子，先取出它们底面的数字(bottom = opp[top])，然后循环 1~6 ，与当前层底面数字不冲突时(!conflict[bottom][i])作为下一层骰子的顶面数字(递归)，返回的方案数也要乘以 $4$ ，因为该层骰子侧面也可以旋转四个方向。

注意：方案数每次更新都要对 1e9+7 取模，否则可能溢出。

时间复杂度： $O(6^n)$ 。

参考：https://www.bilibili.com/video/BV1QE411E7ft?p=52

代码

import java.io.*;

public class Main {
    static final int MOD = (int) 1e9 + 7;
    static final int[] opp = {-1, 4, 5, 6, 1, 2, 3};
    static boolean[][] conflict = new boolean[7][7];
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        in.nextToken();
        int m = (int) in.nval;
        while (m-- > 0) {
            in.nextToken();
            int a = (int) in.nval;
            in.nextToken();
            int b = (int) in.nval;
            conflict[a][b] = true;
            conflict[b][a] = true;
        }
        // 输入完成
        long ans = 0L;
        for (int i = 1; i <= 6; ++i) {
            ans = (ans + dfs(i, n)) % MOD;
        }
        System.out.println(ans);
    }

    static long dfs(int top, int dice) {
        if (dice == 1) return 4;
        long poss = 0L;
        int bottom = opp[top];
        for (int i = 1; i <= 6; ++i) {
            if (conflict[bottom][i]) continue;
            poss = (poss + 4 * dfs(i, dice - 1)) % MOD;
        }
        return poss;
    }
}

方法二：动态规划(超时)

思路

在之前我们发现：垒 $n$ 个骰子的方案数是 $(6^n - k) \times 4^n$ （其中 $k$ 表示面有排斥舍弃的方案数）。
可以看出方案数与 $4^n$ 无关，那么我们可以先忽略骰子侧边的四个面，算出方案数再乘以 $4^n$ 。

于是我们可以从第一层开始递推(动态规划)：

状态：dp[i][j] 表示在第 i 层顶部为数字 j 的骰子的合法方案数。
状态转移方程：
$dp[i][j] = \sum_{x=1}^{6}dp[i-1][x]\ |\ opp[j] 与 x 不冲突$
观察到当前行的状态只与上一行有关，可以使用滚动数组。
初始状态：第一层的骰子以每个数字朝上的方案数都是 $1$ ， $dp[0][1:7]=1$ 。

以输入样例 1 为例：

	1(4)	2(5)	3(6)	4(1)	5(2)	6(3)
1	1	1	1	1	1	1
2	6	6	6	5	5	6

方案数就是最后一行的总和再乘上 $4^n$ ： $4^n \times \sum_{x=1}^{6}dp[n][x]=4^2 \times (6+6+6+5+5+6)=544$ 。

时间复杂度： $O(n)$

参考：https://www.bilibili.com/video/BV1QE411E7ft?p=53

代码

import java.io.*;
import java.util.*;

public class Main {
    static final int MOD = (int) 1e9 + 7;
    static final int[] opp = {-1, 4, 5, 6, 1, 2, 3};
    static boolean[][] conflict = new boolean[7][7];
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        in.nextToken();
        int m = (int) in.nval;
        while (m-- > 0) {
            in.nextToken();
            int a = (int) in.nval;
            in.nextToken();
            int b = (int) in.nval;
            conflict[a][b] = true;
            conflict[b][a] = true;
        }
        // 输入完成
        long[][] dp = new long[2][7]; // 滚动数组
        Arrays.fill(dp[0], 1); // 初始化
        int prev = 1, curr = 0;
        // 迭代层数
        for (int level = 2; level <= n; ++level) {
            // 滚动
            int tmp = prev;
            prev = curr;
            curr = tmp;
            // 尝试在当前层把6个面放在上一层的上方
            // upperTop 表示当前层某骰子A顶部的数字
            for (int upperTop = 1; upperTop <= 6; ++upperTop) {
                // 当前层骰子A的合法方案数
                long poss = 0L;
                // 当前层骰子A底部的数字
                int upperBottom = opp[upperTop];
                for (int lowerTop = 1; lowerTop <= 6; ++lowerTop) {
                    // 当前层骰子A底部与上一层骰子B顶部不冲突时把上一层骰子B的可能方案数累加进 poss
                    if (conflict[lowerTop][upperBottom]) continue;
                    poss = (poss + dp[prev][lowerTop]) % MOD;
                }
                // 更新当前层骰子A的合法方案数
                dp[curr][upperTop] = poss;
            }
        }
        long sum = 0L;
        for (int i = 1; i <= 6; ++i) sum = (sum + dp[curr][i]) % MOD;
        // 快速幂求 4^n
        long ans = 1L, base = 4L;
        while (n != 0) {
            if ((n & 1) != 0) ans = (ans * base) % MOD;
            base = (base * base) % MOD;
            n >>= 1;
        }
        System.out.println((sum * ans) % MOD);
    }
}

#include <iostream>

using namespace std;

const int MOD = 1e9 + 7;
const int opp[] = {-1, 4, 5, 6, 1, 2, 3};
bool conflict[7][7];
long long dp[2][7];

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    while (m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        conflict[a][b] = true;
        conflict[b][a] = true;
    }
    // 输入完成
    for (int i = 1; i <= 6; ++i) dp[0][i] = 1L;
    int prev = 1, curr = 0;
    for (int level = 2; level <= n; ++level) {
        swap(curr, prev);
        for (int upper_top = 1; upper_top <= 6; ++upper_top) {
            long poss = 0L;
            int upper_bottom = opp[upper_top];
            for (int lower_top = 1; lower_top <= 6; ++lower_top) {
                if (conflict[lower_top][upper_bottom]) continue;
                poss = (poss + dp[prev][lower_top]) % MOD;
            }
            dp[curr][upper_top] = poss;
        }
    }
    long long sum = 0L;
    for (int i = 1; i <= 6; ++i) sum = (sum + dp[curr][i]) % MOD;
    // 快速幂
    long long ans = 1L, base = 4L;
    while (n != 0) {
        if ((n & 1) != 0) ans = (ans * base) % MOD;
        base = (base * base) % MOD;
        n >>= 1;
    }
    printf("%lld", (sum * ans) % MOD);

    return 0;
}

目录CONTENT

【DFS, 动态规划】垒骰子【蓝桥杯】

题目

解题

方法一：DFS(超时)

思路

代码

方法二：动态规划(超时)

思路

代码

评论区