牛客网掷骰子问题网易动态规划

秒速五厘米 2022-03-26 13:48 488阅读 0赞

题目：小易参加了一个骰子游戏,这个游戏需要同时投掷n个骰子,每个骰子都是一个印有数字1~6的均匀正方体。小易同时投掷出这n个骰子,如果这n个骰子向上面的数字之和大于等于x,小易就会获得游戏奖励。小易想让你帮他算算他获得奖励的概率有多大。

输入描述：输入包括两个正整数n和x(1 ≤ n < 25, 1 ≤ x < 150),分别表示骰子的个数和可以获得奖励的最小数字和。

输出描述：输出小易可以获得奖励的概率。 如果概率为1,输出1,如果概率为0,输出0,其他以最简分数(x/y)的形式输出。

解题思路：要计算大于x的概率，则需要计算所有骰子点数和的所有可能，以及大于x的所有可能。总数比较容易计算。all\_sum = ![\\small 6^\{^\{n\}\}][small 6_n]，主要的问题是计算大于等于x的数目。暴力解法是计算出所有可能的数目，然后找出大于x的数目，这样时间复杂度是指数级别的。这个题可以比较容易想到用动态规划的方法来求解， 前i个骰子获得大于x的概率与后面的骰子点数没有关系，这就满足动态规划的条件。用数组dp\[i\]\[j\]表示前i个骰子数字之和为j的可能情况，递推公式为dp\[i\]\[j\] = dp\[i\]\[j\] + dp\[i - 1\]\[j - k\]。k为1到6的数。最后的输出是以分数的形式输出，所以在得到总数和大于x的数后需要约分，所以求出二者的最大公约数，然后都除以公约数，得到最后的答案。样例给的数据有点大，需要用long long不然通不过。下面是代码：

#include<iostream>
    #include<vector>
    #include<math.h>
    using namespace std;
    //求最大公约数
    long long gcd(long long a, long long b){
        if(a < b){
            swap(a, b);
        }
        while(a % b != 0){
            long long tem = b;
            b = a % b;
            a = tem;
        }
        return b;
    }
    int main(){
        int n;
        int x;
        while(cin >> n >> x){
            //前i个骰子获得的数字之和为j的掷骰子的数目
            vector<vector<long long>> dp(n + 1, vector<long long> (6 * n + 1, 0));
            long long x_sum = 0;
            dp[0][0] = 1;
            for(int i = 1; i <= n; i++){
                for(int k = 1; k <= 6; k++){
                    for(int j = 1; j <= 6 * n; j++){
                        if(j >= k){
                            dp[i][j] = dp[i][j] + dp[i - 1][j - k];
                        }
                    }
                }
            }
            for(int i = x; i < 6 * n + 1; i++){
    			x_sum += dp[n][i];
            }
    		long long all_sum = pow(6, n);
            if(x_sum == 0){
                cout << 0 << endl;
            }
            else if(x_sum == all_sum){
                cout << 1 << endl;
            }
            else{
                long long gc = gcd(x_sum, all_sum);
                x_sum /= gc;
                all_sum /= gc;
                cout << x_sum << "/" << all_sum << endl;
            }
        }
        return 0;
    }

可以看出时间复杂度是![\\small O(n^\{2\})][small O_n_2]，相对于指数的时间复杂度下降了很多，空间复杂度是![\\small O(n^\{2\})][small O_n_2]。

[small 6_n]: https://private.codecogs.com/gif.latex?%5Csmall%206%5E%7B%5E%7Bn%7D%7D
[small O_n_2]: https://private.codecogs.com/gif.latex?%5Csmall%20O%28n%5E%7B2%7D%29