hihoCoder 1506-投掷硬币

hihoCoder 1506-投掷硬币

#1506 : 投掷硬币

时间限制: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以内都被视为正确。
样例输入
2 1
0.5 0.5
样例输出
0.500000

某枚硬币在第i次投掷时,正面向上的概率为Pi,现在投掷N次,问恰好有M次正面向上的概率是多少。 这一题可以看成有N枚硬币,编号1~N,第i枚硬币正面向上的概率为Pi,把所有硬币一起抛向空中,问落地之后出现M枚正面向上的概率。 我一开始是这么做的,每一枚硬币都有可能正面向上或者反面向上,所以枚举所有2^N种情况,累加所有出现M次正面向上的概率。其实就是DFS,代码如下: [cpp] #include<iostream> #include<cstdlib> #include<algorithm> #include<vector> #include<string> #include<unordered_map> using namespace std; double ans = 0; int n, m; void dfs(const vector<double>& probs, double curprob, int step, int up) { if (up == m) { double oneans = curprob; for (int i = step; i < n; ++i)oneans *= (1 – probs[i]); ans += oneans; return; } if (step < n) { dfs(probs, curprob*probs[step], step + 1, up + 1); dfs(probs, curprob*(1 – probs[step]), step + 1, up); } } int main() { //freopen("input.txt", "r", stdin); scanf("%d %d", &n, &m); vector<double> probs(n, 0); for (int i = 0; i < n; ++i) scanf("%lf", &probs[i]); dfs(probs, 1, 0, 0); printf("%lf\n", ans); return 0; } [/cpp] 不出所料,本代码提交TLE,只能过30%的数据。 其实每一枚硬币都有正面向上或者反面向上的选择,马上想到背包问题,对于每个商品有选或者不选这两种情况,所以本题实际上也是换了个马甲的背包问题。 令dp[i][j]表示前i枚硬币出现j枚正面向上的概率。那么对于第i枚硬币,有两种选择,如果第i枚硬币正面向上,则前i-1枚硬币只能有j-1枚正面向上,即dp[i][j]+=dp[i-1][j-1]*probs[i]。如果第i枚硬币反面向上,则前i-1枚硬币需要有j枚正面向上,所以dp[i][j-1]+=dp[i-1][j-1]*(1-probs[i])。最终返回dp[n][m]。 代码如下: [cpp] #include<iostream> #include<cstdlib> #include<algorithm> #include<vector> #include<string> #include<unordered_map> using namespace std; int main() { //freopen("input.txt", "r", stdin); int n, m; scanf("%d %d", &n, &m); vector<double> probs(n + 1, 0); for (int i = 1; i <= n; ++i)scanf("%lf", &probs[i]); vector<vector<double>> dp(n + 1, vector<double>(n + 1, 0)); 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] * probs[i]; // head dp[i][j – 1] += dp[i – 1][j – 1] * (1 – probs[i]); // tail } } printf("%lf\n", dp[n][m]); return 0; } [/cpp] 本代码提交AC,用时48MS。]]>

Leave a Reply

Your email address will not be published. Required fields are marked *