Atcoder链接：Coins
Luogu链接：Coins
$\scr{\color{BlueViolet}{Solution}}$
观察数据，发现$ \cal{n} \le 3000 $，说明 $ Ο(\cal{n^2}) $可过,容易想到DP。
用 $\cal{dp[i][j]}$ 表示抛完第$\cal{i}$个硬币时，有$\cal{j}$个硬币正面朝上的概率。
考虑$\cal{dp[i][j]}$如何转移，易发现有以下两种情况，（当前正面朝上概率为 $\cal{p_i}$）：
- 本次抛得硬币是正面：抛到正面概率 乘 抛完第$\cal{i-1}$个硬币后，有$j-1$个硬币朝上的概率。
- 本次抛得硬币是反面：抛到反面概率 乘 抛完第$\cal{i-1}$个硬币后，有$j$个硬币朝上的概率。
我们把以上两种情况表示出来，也就是：${dp[i][j]} = {p_i} \times {dp[i-1][j-1]} + {1-p_i} \times {dp[i-1][j]}$
初始值：$\cal{dp[0][0]=1}$，因为第$0$次抽到$0$张卡的概率一定是$1$。
其余$dp[i][j]$值都为0。
然后就好了，最后统计一下符合条件的所有可能情况。
时间复杂度：$\cal{O(n^2)}$
Code:
//From:201929 #include<bits/stdc++.h> #define L long long using namespace std; double a[3005]; double dp[3005][3005]; int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lf",&a[i]); dp[0][0]=1; for(int i=1;i<=n;i++) { for(int j=0;j<=i;j++) { if(i==j) dp[i][j]+=dp[i-1][j-1]*a[i]; else if(j!=0) dp[i][j]+=dp[i-1][j-1]*a[i]+dp[i-1][j]*(1-a[i]); else dp[i][j]+=dp[i-1][j]*(1-a[i]); } } double summ=0; for(int i=1;i<=n;i++) if(i>n-i) summ+=dp[n][i]; printf("%.9lf",summ); return 0; }