【hihocoder #1506 : 投掷硬币】递推

本文主要是介绍【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
【思路】：见代码
【代码】：


/*********************************
*   Date：    2017-04-16 12:00
*   Author：  herongwei
*   Problem:  投掷硬币
*   Source：  https://hihocoder.com/problemset/problem/1506
*   Result：  AC 
*   Language: G++
*********************************
描述
小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
*/
#pragma comment(linker,"/STACK:102400000,102400000")
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <set>
#include <stack>
#include <math.h>
#include <map>
#include <queue>
#include <deque>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;
const int maxm = 55;
const LL MOD = 999999997;
int dir4[4][2]= {{1,0},{0,1},{-1,0},{0,-1}};
int dir8[8][2]= {{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};
inline int read()
{int  c=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}return c*f;
}
double dp[1050][1050];
int main()
{//freopen("in2.txt", "r", stdin);int n,m;while(scanf("%d%d",&n,&m)!=EOF){dp[0][0]=1.0; ///dp[i][j] 表示硬币投掷n次恰好m次正面朝上概率for(int i=0; i<n; ++i)///枚举投掷n次{double p; ///第i次投掷这枚硬币时，正面向上的概率是Piscanf("%lf",&p);for(int j=0; j<=i; ++j) ///枚举前i次硬币正面朝上状态{dp[i+1][j]+=dp[i][j]*(1.0-p); ///投掷i+1次j次正面朝上的概率=当前概率+投掷i次j次正面朝上概率dp[i+1][j+1]+=dp[i][j]*p;///投掷i+1次j+1次正面朝上的概率=当前概率+投掷i次j次正面朝上的概率}} printf("%.6f\n",dp[n][m]); ///硬币投掷n次恰好m次正面朝上概率}return 0;
}