题解 | #骰子游戏#

解题思路

这是一个概率DP问题：

1. 个骰子同时投掷，每个骰子点数为
2. 如果所有骰子点数和大于等于 ，则获得奖励
3. 需要计算获得奖励的概率

解题步骤：

1. 使用 dp[i][j] 表示投 个骰子和为 的方案数
2. 状态转移：dp[i][j] = sum(dp[i-1][j-k])， 从 到
3. 计算概率：获奖方案数/总方案数
4. 化简分数到最简形式

代码

#include <iostream>
using namespace std;

const int MAXN = 26;
const int MAXX = 151;

int main() {
    int n, x;
    cin >> n >> x;
    
    // dp[i][j]: i个骰子和为j的方案数
    long long dp[MAXN][MAXX] = {0};
    
    // 初始化
    dp[0][0] = 1;
    
    // 动态规划
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n * 6; j++) {
            // 枚举当前骰子的点数
            for (int k = 1; k <= 6; k++) {
                if (j >= k) {
                    dp[i][j] += dp[i-1][j-k];
                }
            }
        }
    }
    
    // 计算分子分母
    long long total = 0, favorable = 0;
    for (int i = n; i <= n * 6; i++) {
        total += dp[n][i];
    }
    for (int i = x; i <= n * 6; i++) {
        favorable += dp[n][i];
    }
    
    // 特殊情况处理
    if (favorable == total) {
        cout << "1" << endl;
        return 0;
    }
    if (favorable == 0) {
        cout << "0" << endl;
        return 0;
    }
    
    // 求最大公约数并化简
    long long a = favorable, b = total;
    while (a % b != 0) {
        long long c = a % b;
        a = b;
        b = c;
    }
    cout << favorable/b << "/" << total/b << endl;
    
    return 0;
}

import java.util.Scanner;

public class Main {
    static final int MAXN = 26;
    static final int MAXX = 151;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int x = sc.nextInt();
        
        // dp[i][j]: i个骰子和为j的方案数
        long[][] dp = new long[MAXN][MAXX];
        
        // 初始化
        dp[0][0] = 1;
        
        // 动态规划
        for (int i = 1; i <= n; i++) {
            for (int j = i; j <= n * 6; j++) {
                for (int k = 1; k <= 6; k++) {
                    if (j >= k) {
                        dp[i][j] += dp[i-1][j-k];
                    }
                }
            }
        }
        
        // 计算分子分母
        long total = 0, favorable = 0;
        for (int i = n; i <= n * 6; i++) {
            total += dp[n][i];
        }
        for (int i = x; i <= n * 6; i++) {
            favorable += dp[n][i];
        }
        
        // 特殊情况处理
        if (favorable == total) {
            System.out.println("1");
            return;
        }
        if (favorable == 0) {
            System.out.println("0");
            return;
        }
        
        // 求最大公约数并化简
        long a = favorable, b = total;
        while (a % b != 0) {
            long c = a % b;
            a = b;
            b = c;
        }
        System.out.println(favorable/b + "/" + total/b);
        
        sc.close();
    }
}

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

# 读入数据
n, x = map(int, input().split())

# dp[i][j]: i个骰子和为j的方案数
dp = [[0] * (n * 6 + 1) for _ in range(n + 1)]
dp[0][0] = 1

# 动态规划
for i in range(1, n + 1):
    for j in range(i, n * 6 + 1):
        for k in range(1, 7):
            if j >= k:
                dp[i][j] += dp[i-1][j-k]

# 计算分子分母
total = sum(dp[n][n:n*6+1])
favorable = sum(dp[n][x:n*6+1])

# 特殊情况处理
if favorable == total:
    print("1")
elif favorable == 0:
    print("0")
else:
    # 化简分数
    g = gcd(favorable, total)
    print(f"{favorable//g}/{total//g}")

算法及复杂度

• 算法：动态规划
• 时间复杂度：，其中 是骰子个数
• 空间复杂度：，用于存储dp数组