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,代码如下:

#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;
}

不出所料,本代码提交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]。

代码如下:

#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;
}

本代码提交AC,用时48MS。

Leave a Reply

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