【LightOJ】1064 - Throwing Dice（dp打表）
【LightOJ】1064 - Throwing Dice（dp打表）
点击打开题目
1064 - Throwing Dice
PDF (English) | Statistics | Forum |
|---|
Time Limit: 2 second(s) | Memory Limit: 32 MB |
|---|
n common cubic dice are thrown. What is the probability 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.
Sample Input | Output for Sample Input |
|---|---|
7 3 9 1 7 24 24 15 76 24 143 23 81 7 38 | Case 1: 20/27 Case 2: 0 Case 3: 1 Case 4: 11703055/78364164096 Case 5: 25/4738381338321616896 Case 6: 1/2 Case 7: 55/46656 |
一直在想排列与组合的问题，比赛快结束想到了dp然而没时间了，挺亏的。
代码如下：
#include <cstdio>
#include <stack>
#include <cmath>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
LL GCD(LL a,LL b)
{
return b == 0 ? a : GCD(b , a%b);
}
int main()
{
LL dp[26][155] = {0};
for (int i = 6 ; i ; i--)
dp[1][i] = 1;
for (int i = 2 ; i <= 25 ; i++)
{
for (int j = i * 6 ; j >= i ; j--)
{
for (int k = j-1 ; k >= j - 6 && k > 0 ; k--)
dp[i][j] += dp[i-1][k];
}
}
int u;
int n,x;
int Case = 1;
scanf ("%d",&u);
while (u--)
{
scanf ("%d %d",&n,&x);
printf ("Case %d: ",Case++);
if (x > n*6)
{
puts("0");
continue;
}
else if (x <= n)
{
puts("1");
continue;
}
LL sum1 = 0;
for (int i = x ; i <= n*6 ; i++)
sum1 += dp[n][i];
LL sum2 = pow(6.0,n);
LL g = GCD(sum1 , sum2);
printf ("%lld/%lld\n",sum1/g,sum2/g);
}
return 0;
}腾讯云开发者
