首页 > 代码库 > codeves 1060 搞笑世界杯
codeves 1060 搞笑世界杯
1060 搞笑世界杯
随着世界杯小组赛的结束,法国,阿根廷等世界强队都纷纷被淘汰,让人心痛不已. 于是有
人组织了一场搞笑世界杯,将这些被淘汰的强队重新组织起来和世界杯一同比赛.你和你的朋
友欣然去购买球票.不过搞笑世界杯的球票出售方式也很特别,它们只准备了两种球票.A 类
票------免费球票 B 类票-------双倍价钱球票.购买时由工作人员通过掷硬币决定,投到正面
的买A类票, 反面的买B类票.并且由于是市场经济,主办方不可能倒贴钱,所以他们总是准备
了同样多的A类票和B类票.你和你的朋友十分幸运的排到了某场精彩比赛的最后两个位置.
这时工作人员开始通过硬币售票.不过更为幸运的是当工作人员到你们面前时他发现已无需
再掷硬币了,因为剩下的这两张票全是免费票。
你和你的朋友在欣喜之余,想计算一下排在队尾的两个人同时拿到一种票的概率是多少
(包括同时拿A 类票或B类票) 假设工作人员准备了2n 张球票,其中n 张A类票,n 张B类票,并且排在队伍中的人每人必须且只能买一张球票(不管掷到的是该买A 还是该买B).
输入文件仅一行,包含球票数2n . 其中,0<n<=1250 ,n 为整数。
输出文件只包含一个数,为拿到同一种票的概率,精确到小数点后4 位。
256
0. 9500
思路:他给出的n其实就是总票数,中文题意。。。,
dp[i][j]表示前i个人有j个A票的,那么答案就是dp[n-2][n/2]*2(可以全A或者全B)
转移方程:dp[i][j]=dp[i-1][j-1]*0.5+dp[i-1][j]*0.5;
当j==n/2时,后面肯定必然为B票,所以dp[i][j]=dp[i-1][j-1]*0.5+dp[i-1][j].
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 double dp[3000][3000]; 5 6 int main(){ 7 int n; 8 scanf("%d",&n); 9 dp[0][0]=1; 10 for(int i=1;i<=n;i++){ 11 dp[i][0]=dp[i-1][0]*0.5; 12 for(int j=0;j<=n/2;j++){ 13 if(j==n/2) dp[i][j]=dp[i-1][j-1]*0.5+dp[i-1][j]; 14 else dp[i][j]=dp[i-1][j-1]*0.5+dp[i-1][j]*0.5; 15 } 16 } 17 printf("%.4lf\n",dp[n-2][n/2]*2); 18 }
codeves 1060 搞笑世界杯