lightoj 1064 动态规划

爱被打了一巴掌 2022-07-28 01:09 129阅读 0赞

1064 - Throwing Dice

<table> 
 <tbody> 
  <tr> 
   <td title="normal judge"><a href="http://lightoj.com/volume_submit.php?problem=1064" rel="nofollow"><img src="http://lightoj.com/images/submit1.png" alt=""> </a>&nbsp; <a href="http://udebug.com/LOJ/1064" rel="nofollow"><img src="http://lightoj.com/images/udebug.png" alt=""> </a></td> 
   <td><a href="http://lightoj.com/volume_showproblem.php?problem=1064&amp;language=english&amp;type=pdf" rel="nofollow">PDF (English) </a></td> 
   <td><a href="http://lightoj.com/volume_problemstat.php?problem=1064" rel="nofollow">Statistics </a></td> 
   <td><a href="http://lightoj.com/forum_showproblem.php?problem=1064" rel="nofollow">Forum </a></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td>Time Limit: <span style="color:#B45F04">2 second(s)</span></td> 
   <td>Memory Limit: <span style="color:#B45F04">32 MB</span></td> 
  </tr> 
 </tbody> 
</table>

**n** common cubic dice are thrown. What is theprobability that the sum of all thrown dice is at least **x**?

# Input #

Input starts with an integer **T (≤ 200)**,denoting the number of test cases.

Each test case contains two integers **n (1 ≤ n <25)** and  **x (0 ≤ x < 150)**. The meanings of **n** and **x**are given in the problem statement.

# Output #

For each case, output the case number and the probability in**'p/q'** form where **p** and **q** are relatively prime. If **q**equals **1** then print **p** only.

<table> 
 <tbody> 
  <tr> 
   <td> <h1>Sample Input</h1> </td> 
   <td> <h1>Output for Sample Input</h1> </td> 
  </tr> 
  <tr> 
   <td> <p>7</p> <p>3 9</p> <p>1 7</p> <p>24 24</p> <p>15 76</p> <p>24 143</p> <p>23 81</p> <p>7 38</p> </td> 
   <td> <p>Case 1: 20/27</p> <p>Case 2: 0</p> <p>Case 3: 1</p> <p>Case 4: 11703055/78364164096</p> <p>Case 5: 25/4738381338321616896</p> <p>Case 6: 1/2</p> <p>Case 7: 55/46656</p> </td> 
  </tr> 
 </tbody> 
</table>

题意: 有n个骰子,把他们扔出去, 求朝上的面的数的和相加至少是x 的概率是多少;

分析: 很有意思的题目, 有n个骰子, 总的情况肯定就是6的n次方. 然后求符合条件的情况;

我们用dp来求解这个情况, 用dp\[i\]\[j\] 来表示扔第i个骰子总和为j的数目, 那么就会有

dp\[i\]\[j\] = dp\[i-1\]\[j-k\] (1<=k<=6);

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    #define F first
    #define S second
    using namespace std;
    
    typedef unsigned long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;int f=1;
        while((c=getchar())<'0' || c>'9')if(c=='-')f=-1;
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res*f;
    }
    const int N=100010;
    int n,x;
    
    ll dp[25][151];
    ll gcd(ll a,ll b)
    {
        return b? gcd(b,a%b):a;
    }
    ll power(ll a,int n)
    {
        ll ret=1;
        while(n)
        {
            if(n & 1) ret *= a;
            a *= a;
            n>>=1;
        }
        return ret;
    }
    int main()
    {
        int T=in(),ca=1;
        while(T--)
        {
            n=in(),x=in();
            mem(dp,0);
            for(int i=1;i<=6;i++) dp[1][i]=1;
            for(int i=1;i<n;i++)
            {
                for(int j=1;j<=150;j++)
                {
                    if(!dp[i][j]) continue;
                    for(int k=1;k<=6;k++)
                    {
                        dp[i+1][j+k] += dp[i][j];
                    }
                }
            }
            ll all=power(6,n),t=0;
            for(int i=x;i<=150;i++)
            {
                t += dp[n][i];
            }
            if(t==all) printf("Case %d: 1\n",ca++);
            else if(t==0) printf("Case %d: 0\n",ca++);
            else{
                ll g=gcd(t,all);
                printf("Case %d: %llu/%llu\n",ca++,(t/g),(all/g));
            }
        }
        return 0;
    }