投掷硬币（概率dp）

小Hi有一枚神奇的硬币。已知第i次投掷这枚硬币时，正面向上的概率是P_i。

现在小Hi想知道如果总共投掷N次，其中恰好M次正面向上的概率是多少。

Input

第一行包含两个整数N和M。

第二行包含N个实数P₁, P₂, ... P_N。

对于30%的数据，1 <= N <= 20

对于100%的数据，1 <= N <= 1000, 0 <= M <= N, 0 <= P_i <= 1

Output

输出一行一个实数表示恰好M次正面向上的概率。注意行末需要包含一个换行符' '。

输出与标准答案误差在0.001以内都被视为正确。

Sample Input

2 1
0.5 0.5

Sample Output

0.500000

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 
 8 int n,m;
 9 float p[1005];
10 float dp[1005][1005];
11 //x[i][j] 表示投掷i次,j次正面的概率； 概率dp
12 
13 int main()
14 {
15     scanf("%d%d",&n,&m);
16     for(int i=1;i<=n;i++)
17         scanf("%f",&p[i]);
18 
19     dp[0][0]=1;
20     for(int i=1;i<=n;i++)
21     {
22         for(int j=1;j<=m+1 ;j++)  //j<=m+1 多弄一次，在j-1=m的时候投不中正面
23         {
24             dp[i][j] += dp[i-1][j-1]*p[i];
25             //投掷i次j次正面+= 第i次投并且是正面
26             dp[i][j-1] += dp[i-1][j-1]*(1-p[i]);
27             //投掷i次j-1次正面+= 第i次投并且恰好不是正面
28         }
29     }
30     printf("%.6f
",dp[n][m]);
31 }

2018-03-07