louisfghbvc的部落格

題目連結:   https://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=2993

題目大意:  給你n顆骰子，問總和至少n的機率為多少

思路:  動態規劃，建表。見兩個表一個是6的n次方，一個是dp[n][x]。dp表示能用n顆骰子總和為x的方法有幾種。

其實這題是硬幣dp題的變形。狀態轉移為dp[i][k] += dp[i-1][k-j]。意思為第i顆骰子總和k，為第i-1顆骰子總和-點數(1-6)而來。

可以自己畫圖想想囉 !

代碼:  

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

LL dp[25][200];
LL pow6[25];

int main()
{
    int n, x;
    memset(dp, 0, sizeof dp);
    dp[0][0] = 1;
    for(int i = 1; i <= 20; ++i){
        for(int j = 1; j <= 6; ++j){
            for(int k = (i-1)+j; k <= 6*(i-1)+j; ++k){
                dp[i][k] += dp[i-1][k-j];
            }
        }
    }
    pow6[0] = 1;
    for(int i = 1; i <= 20; ++i)
        pow6[i] = 6*pow6[i-1];

    cin >> n >> x;
    LL d = pow6[n], u = 0;
    for(int k = x; k <= 6*n; ++k)
        u += dp[n][k];
    LL gcd = __gcd(d, u);
    if(u)
        cout << u/gcd << " / " << d/gcd << endl;
    else
        puts("0");
    return 0;
}
/*
3 9
7 38
20 130
20 56
10 40
*/