题目大意

$N$ 枚硬币，第 $i$ 枚硬币有 $p_i$ 的概率正面朝上，有 $1-p_i$ 的概率反面朝上。
扔完所有硬币，求正面朝上的银币数比反面朝上的银币数多的概率，其中 $N\le 2999$。

思路

显而易见的这道题目是一个 DP，绝对不是因为它是 DP 列表里的题目。因为题目中的 $N\le 2999$ 所以可以考虑 $n^2$ 的DP 程序。

设 $f_{i,j}$ 表示正面有 $i$ 个硬币，反面有 $j$ 个硬币的概率。

得到有 $i$ 个正面，$j$ 个反面只有可能是由 $i-1$ 个正面与 $j$ 个反面通过投掷一个正面或者 $i$ 个正面与 $j-1$ 个反面通过投掷一个反面得到的。

所以 $f_{i,j}=f_{i-1,j}\times p_{i+j}+f_{i,j-1}\times (1-p_{i+j})$。

AC Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3005;
int n;
double p[N],f[N][N],ans;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>p[i];
	f[0][0]=1.0;
	for(int i=1;i<=n;i++){
		f[i][0]=f[i-1][0]*p[i];
		f[0][i]=f[0][i-1]*(1-p[i]);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j+i<=n;j++){
			f[i][j]=f[i-1][j]*p[i+j]+f[i][j-1]*(1-p[i+j]);
		}
	}
	for(int i=n/2+1;i<=n;i++){
		ans+=f[i][n-i];
	}printf("%.10lf",ans);
	return 0;
}