LightOJ1064 Throwing Dice（DP）
第一眼以为是概率DP，我还不会。不过看题目那么短就读读，其实这应该还不是概率DP，只是个水水的DP。。
- dp[n][s]表示掷n次骰子点数和为s的情况数
- dp[0][0]=1
- dp[i][j]=∑dp[i-1][j-k] （k∈[1,6] 且 j-k>=0）
要求的概率就是情况数/掷n次骰子的总情况数，掷n次骰子总情况数就是6n。
最后的结果分子分母要互质，而分母的质因子只有2和3，所以只要同除以2和3就能化简。
1 #include<cstdio> 2 using namespace std; 3 long long d[25][151]; 4 int main(){ 5 d[0][0]=1; 6 for(int i=1; i<25; ++i){ 7 for(int j=1; j<=150; ++j){ 8 for(int k=1; k<=6; ++k){ 9 if(j-k>=0) d[i][j]+=d[i-1][j-k]; 10 } 11 } 12 } 13 int t,a,b; 14 scanf("%d",&t); 15 for(int cse=1; cse<=t; ++cse){ 16 scanf("%d%d",&a,&b); 17 long long p=0,q=1; 18 for(int i=b; i<=150; ++i) p+=d[a][i]; 19 for(int i=1; i<=a; ++i) q*=6; 20 if(p==0){ 21 printf("Case %d: 0\n",cse); 22 continue; 23 } 24 while(p%2==0 && q%2==0){ 25 p/=2; q/=2; 26 } 27 while(p%3==0 && q%3==0){ 28 p/=3; q/=3; 29 } 30 if(q==1){ 31 printf("Case %d: 1\n",cse); 32 continue; 33 } 34 printf("Case %d: %lld/%lld\n",cse,p,q); 35 } 36 return 0; 37 }优质内容筛选与推荐>>
1、背包问题
2、选择排序（直接选择、堆排序）
3、WPF Tag
4、Python练习 - 用户登录
5、javaMail发送邮件