5、垒骰子

题目 垒骰子

思路分析

分析发现可以用dp

dp[i][j] 第i个骰子 以j为底（j的反为顶） 的放法的方案数 count

对于每一个骰子为底的情况 可以从上一层不冲突的骰子状态转移而来 数量应该是它们的总和

又因为固定底面 实际是有4种方式的 （可以旋转）所以应该是对上一层某个状态*4 再做累加

状态转移：for(k:1-6) if(不冲突）dp[i][j] += 4*dp[i-1][k];

初始化状态 对于第一个骰子 6个面都可以为底 每个面为底的方案数都有4种

for (int i = 1; i <= 6; ++i) dp[0][i] = 4;

往后优化我应该是想不到的 听都没听过

代码实现

过3/5

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

typedef pair<int,int> PII;

const int MOD = 1e9 + 7;

LL dp[2][7]; //dp[i][j] 第i个骰子 以j为底(j的反为顶)的放法的方案数 count 每层只需上次 滚动

set<PII> limit;

int reverseAspect[7];

int back(int x) {

    if(x == 1) return 4;

    if(x == 2) return 5;

    if(x == 3) return 6;

    if(x == 4) return 1;

    if(x == 5) return 2;

    if(x == 6) return 3;

    return 0;

}

int main() {

    int n, m;

    cin >> n >> m;

    for (int i = 0; i < m; ++i) {

        int a, b;

        cin >> a >> b;

        limit.insert({a, b});

        limit.insert({b, a});

    }

    for (int i = 1; i <= 6; ++i) {

        dp[0][i] = 4;// 初始化第一个骰子的每一面作为底面的放置方案数 确定底面还可以旋转4次

    }

    int curr = 0;

    for (int i = 2; i <= n; ++i) {//枚举骰子

        curr = 1 - curr;

        for (int j = 1; j <= 6; ++j) {//当前骰子的状态

            dp[curr][j] = 0;// 初始化当前状态

            for (int k = 1; k <= 6; ++k) { //上一个骰子的状态

                if (!limit.count({back(j), k})) {//如果能放 那么就是 之前每种可放的方案数*4 之和

                    dp[curr][j] += 4*dp[1 - curr][k];

                    dp[curr][j] %= MOD;

                }

            }

        }

    }

    long long sum = 0;

    for (int i = 1; i <= 6; ++i) { // 累加最后一个骰子每一面作为底面的放置方案数

        sum += dp[curr][i];

        sum %= MOD;

    }

    cout << sum << endl;

    return 0;

}

同类题型

视频讲解

⬅️ 4、移动距离 🏠 00-刷题理模型 ➡️ 6、生命之树