时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

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

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

输入

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

第二行包含N个实数P1, P2, … PN

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

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

输出

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

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

样例输入

样例输出


简单概率DP

二维数组dp[i][j]表示现在抛了i个硬币j个朝上

自然由递推关系得出dp[i][j]=dp[i-1][j]*(1-p[i])+d[i-1][j]*p[i]

当然也可以转化成一维的数组

下面贴出代码



2019-07-21  10:27:20  Author: WindCry1



分类: DP

0 条评论

发表评论

邮箱地址不会被公开。 必填项已用*标注