时间限制: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以内都被视为正确。
样例输入
|
1 2 |
2 1 0.5 0.5 |
样例输出
|
1 |
0.500000 |
简单概率DP
二维数组dp[i][j]表示现在抛了i个硬币j个朝上
自然由递推关系得出dp[i][j]=dp[i-1][j]*(1-p[i])+d[i-1][j]*p[i]
当然也可以转化成一维的数组
下面贴出代码
|
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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
/************************************************************************* >>> Author: WindCry1 >>> Mail: lanceyu120@gmail.com >>> Website: https://windcry1.com >>> Date: 7/21/2019 10:13:30 AM *************************************************************************/ #include<cstring> #include<cmath> #include<cstdio> #include<cctype> #include<cstdlib> #include<ctime> #include<vector> #include<iostream> #include<string> #include<queue> #include<set> #include<map> #include<algorithm> #include<complex> #include<stack> #include<bitset> #include<iomanip> #include<list> #if __cplusplus >= 201103L #include<unordered_map> #include<unordered_set> #endif #define ll long long #define ull unsigned long long using namespace std; const double clf=1e-8; const int MMAX=0x7fffffff; const int INF=0xfffffff; const int mod=1e9+7; double p[1010]; double dp[1010]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); //freopen("C:\\Users\\LENOVO\\Desktop\\in.txt","r",stdin); //freopen("C:\\Users\\LENOVO\\Desktop\\out.txt","w",stdout); int n,m; cin>>n>>m; for(int i=1;i<=n;i++) cin>>p[i]; dp[0]=1; for(int i=1;i<=n;i++) for(int j=m;j>=0;j--) dp[j]=dp[j]*(1-p[i])+dp[j-1]*p[i]; cout<<dp[m]<<endl; return 0; } |
2019-07-21 10:27:20 Author: WindCry1
0 条评论