洛谷题解 P2719 搞笑世界杯

搞笑世界杯

题目背景

很久很久以后，一次世界杯。

题目描述

随着世界杯小组赛的结束，法国，阿根廷等世界强队都纷纷被淘汰，让人心痛不已。 于是有人组织了一场搞笑世界杯，将这些被淘汰的强队重新组织起来和世界杯一同比赛。你和你的朋友欣然去购买球票。不过搞笑世界杯的球票出售方式也很特别，它们只准备了两种球票。

• A 类票——免费球票
• B 类票——双倍价钱球票。

购买时由工作人员通过掷硬币决定，投到正面的买 A 类票， 反面的买 B 类票。由于是市场经济，主办方不可能倒贴钱，所以他们总是准备了同样多的 A 类票和 B 类票。你和你的朋友十分幸运的排到了某场精彩比赛的最后两个位置。

这时工作人员开始通过硬币售票。不过更为幸运的是当工作人员到你们面前时他发现已无需再掷硬币了，因为剩下的这两张票全是免费票。

你和你的朋友在欣喜之余，想计算一下排在队尾的两个人同时拿到一种票的概率是多少(包括同时拿 A 类票或 B 类票) 假设工作人员准备了 $2n$ 张球票，其中 $n$ 张 A 类票，$n$ 张 B 类票，并且排在队伍中的人每人必须且只能买一张球票(不管掷到的是该买 A 还是该买 B)。

输入格式

输入文件仅一行，包含整数 $2n$，代表 A、B 类票各 $n$ 张。其中，$0\le n\le 1250$ ，$n$ 为整数。

输出格式

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

样例 #1

样例输入 #1

256
1

样例输出 #1

0.9500
1

动态规划，dp[i][j]为剩i张A票和j张B票时队尾同票的概率，初始dp[2][0]和dp[0][2]为100%

代码：

#include
int main()
{
	int n,i,j;
    double d[1500][1500];
	scanf("%d",&n);
	n=n/2;
	for (i=2;i<=n;i++)
	{
		d[i][0]=d[0][i]=1;
	}
	for (i=1;i<=n;i++)
	{
		for (j=1;j<=n;j++)
		{
			d[i][j]=(d[i-1][j]+d[i][j-1])*0.5000;
		}
	}
	printf ("%.4lf",d[n][n]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21