欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

codevs1060 搞笑世界杯(dp)

程序员文章站 2024-01-12 09:34:22
...

题目描述 Description
随着世界杯小组赛的结束,法国,阿根廷等世界强队都纷纷被淘汰,让人心痛不已. 于是有

人组织了一场搞笑世界杯,将这些被淘汰的强队重新组织起来和世界杯一同比赛.你和你的朋

友欣然去购买球票.不过搞笑世界杯的球票出售方式也很特别,它们只准备了两种球票.A 类

票——免费球票 B 类票——-双倍价钱球票.购买时由工作人员通过掷硬币决定,投到正面

的买A类票, 反面的买B类票.并且由于是市场经济,主办方不可能倒贴钱,所以他们总是准备

了同样多的A类票和B类票.你和你的朋友十分幸运的排到了某场精彩比赛的最后两个位置.

这时工作人员开始通过硬币售票.不过更为幸运的是当工作人员到你们面前时他发现已无需

再掷硬币了,因为剩下的这两张票全是免费票。

你和你的朋友在欣喜之余,想计算一下排在队尾的两个人同时拿到一种票的概率是多少

(包括同时拿A 类票或B类票) 假设工作人员准备了2n 张球票,其中n 张A类票,n 张B类票,并且排在队伍中的人每人必须且只能买一张球票(不管掷到的是该买A 还是该买B).

输入描述 Input Description
输入文件仅一行,包含球票数2n . 其中,0< n<=1250 ,n 为整数。

输出描述 Output Description
输出文件只包含一个数,为拿到同一种票的概率,精确到小数点后4 位。

样例输入 Sample Input
256

样例输出 Sample Output
0. 9500

思路:假设dp[i][j] 表示a类票剩余i张,b类票剩余j张时队尾两人拿到相同票的概率,那么状态转移方程即为 dp[i][j]=dp[i-1][j]*0.5+dp[i][j-1]*0.5(此时队首的人拿a,b类票的概率都为0.5) ,然后当a,b类票中某一类票的数量为0,另一个票的数量大于等于2时,那么剩下的人肯定拿的都是相同的票,所以概率为1.

代码如下

#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <cmath>  
#include <algorithm>
#define LL long long int 
using namespace std;  
double dp[2000][2000];
int main()
{
    int n;
    scanf("%d",&n);
    n/=2;//注意题目给你的是两种票的数量的总和
    for(int i=2;i<=n;i++)
    dp[i][0]=dp[0][i]=1;

    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    dp[i][j]=(dp[i-1][j]+dp[i][j-1])*0.5;

    printf("%.4lf\n",dp[n][n]);
    return 0;
}