搞笑世界杯

P2719 搞笑世界杯 - 洛谷

---

题型分析

二维概率DP+生日问题变种

题目描述&数据范围

题解

显然当一种票卖完后，卖剩下一种票的概率会变为 $1$

讨论这种不统一的情况会非常困难

所以不妨反过来考虑，求最后剩下两种票的概率

这样保证了前 $n-2$ 张票一定是以 $\frac{1}{2}$ 的概率卖出的

设 $p[i][j]$ 表示 有 $i$ 张 $A$ 类票和 $j$ 张 $B$ 类票时的答案

显然边界条件： $p[0][1]=p[1][0]=1$

转移方程：
$$
p[i][j]=0.5(p[i-1][j]+p[i][j-1])
$$

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e3+10;
double p[maxn][maxn];

void solve(){
	int n;cin>>n;
	n/=2;
	p[0][1]=p[1][0]=1;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			p[i][j]=0.5*(p[i-1][j]+p[i][j-1]);
		}
	}
	cout<<fixed<<setprecision(4);
	cout<<1-p[n][n]<<'\n';
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	//fstream in("in.txt",ios::in);cin.rdbuf(in.rdbuf());
	int t=1;//cin>>t;
	while(t--)solve();
	return 0;
}