hihoCoder 1506-投掷硬币

---

某枚硬币在第i次投掷时，正面向上的概率为P_i，现在投掷N次，问恰好有M次正面向上的概率是多少。 这一题可以看成有N枚硬币，编号1~N，第i枚硬币正面向上的概率为P_{i，把所有硬币一起抛向空中，问落地之后出现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。]]>