1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/*
Author: herongwei
Source: github.com/rongweihe
思路：
每一枚硬币都有正面向上或者反面向上的选择，想到背包问题，对于每个商品有选或者不选这两种情况，所以本题实际上也是背包问题。
令dp[i][j]表示前i枚硬币出现j枚正面向上的概率。
那么对于第i枚硬币，有两种选择
如果第i枚硬币正面向上，则前i-1枚硬币只能有j-1枚正面向上，即dp[i][j]+=dp[i-1][j-1]*p[i]。
如果第i枚硬币反面向上，则前i-1枚硬币需要有j枚正面向上，所以dp[i][j-1]+=dp[i-1][j-1]*(1-p[i])。
最终返回dp[n][m]。
*/
#include<bits/stdc++.h>
using namespace std;
int main()
{
    //freopen("input.txt", "r", stdin);
    int n, m;
    scanf("%d %d", &n, &m);
    double p[n + 1] = {0.0};
    double dp[n+1][n+1] = {0.0};
    for(int i = 1; i <= n; ++i)
        scanf("%lf", &p[i]);
    dp[0][0] = 1.0;
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= i; ++j)   //现在有i枚硬币，所以正面向上的个数j不超过i
        {
            dp[i][j] += dp[i - 1][j - 1] * p[i];  // head
            dp[i][j - 1] += dp[i - 1][j - 1] * (1 - p[i]); // tail
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX