题目来源：
https://www.nowcoder.com/practice/0e83797c34e54cca91179fe9ad681bc4?tpId=90&tqId=30849&tPage=4&rp=4&ru=%2Fta%2F2018test&qru=%2Fta%2F2018test%2Fquestion-ranking
题目描述：
小易参加了一个骰子游戏,这个游戏需要同时投掷n个骰子,每个骰子都是一个印有数字1~6的均匀正方体。
小易同时投掷出这n个骰子,如果这n个骰子向上面的数字之和大于等于x,小易就会获得游戏奖励。
小易想让你帮他算算他获得奖励的概率有多大。
思路：
1
2
3
4
5
| 动态规划，用dp[i][j]表示i个骰子产生数字和j的结果数，
初始值dp[1][j]=1(j=1~6),dp[i] [i]=1,dp[i][6*i]=1,
由于第i个骰子的点数可以为1~6，要使i个骰子的数字和为j的话，
则前i-1个骰子的数字和可以为j-1~j-6，
所以得到公式dp[i][j] +=dp[i-1][j-k] (k=1~6)。
|
参考代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| public class Now_73 {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int x=sc.nextInt();
if(n>=x) System.out.print(1);
else if(6*n<x) System.out.print(0);
else {
long[][] dp=new long[n+1][6*n+1];
for(int i=1;i<=6;i++) dp[1][i]=1;
for(int i=2;i<=n;i++) {
for(int j=i;j<=6*n;j++) {
for(int k=1;k<j&&k<=6;k++) {
dp[i][j]+=dp[i-1][j-k];
}
}
}
long total=(long)Math.pow(6,n);
long sum=0;
for(int i=1;i<x;i++) sum+=dp[n][i];
long num=gcd(total-sum,total);
System.out.print((total-sum)/num+"/"+total/num);
}
}
private static long gcd(long a,long b) {
return (a%b==0)?b:gcd(b,a%b);
}
}
|
