硬币投掷实验c语言程序设计,投掷硬币（动态规划）

浅浅的花香味﹌ 2022-10-14 13:49 182阅读 0赞

\#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

AC code：

\#include

\#include

\#include

\#include

\#include

\#include

\#include

\#include

\#include

\#include

\#define MAXN 1000010

\#define EPS 1e-9

using namespace std;

double pi\[1010\],dp\[1001\]\[1001\];

int n,m;

int main()

\{

//freopen("D:\\\\in.txt","r",stdin);

int i,j;

while(scanf("%d%d",&n,&m)!=EOF)

\{

for(i=1;i<=n;i++)

\{

scanf("%lf",&pi\[i\]);

\}

memset(dp,0,sizeof(dp));

dp\[1\]\[1\]=pi\[1\];

dp\[1\]\[0\]=1-pi\[1\];

for(i=2;i<=n;i++)

\{

dp\[i\]\[0\]=dp\[i-1\]\[0\]\*(1-pi\[i\]);

\}

for(i=2;i<=n;i++)

\{

for(j=1;j<=i;j++)

\{

dp\[i\]\[j\]=dp\[i-1\]\[j\]\*(1-pi\[i\])+dp\[i-1\]\[j-1\]\*pi\[i\];

\}

\}

printf("%lf\\n",dp\[n\]\[m\]);

\}

return 0;

\}

发表评论取消回复

表情：

评论列表（有 0 条评论，182人围观）

还没有评论，来说两句吧...

相关阅读

相关 C语言：收集硬币（动态规划，回溯）

![b6792e074d447d5ba0bfa2d39e4c187a.png][] 目录动态规划求解收集硬币（‘超’详细介绍）问题引入

刺骨的言语ヽ痛彻心扉/ 2023年07月20日 05:55/ 0 赞/ 88 阅读

相关 c语言换硬币

将一笔零钱换成5分、2分和1分的硬币，要求每种硬币至少有一枚，有几种不同的换法？将一笔零钱换成5分、2分和1分的硬币，要求每种硬币至少有一枚，有几种不同的换法？输入

忘是亡心i/ 2023年07月15日 11:25/ 0 赞/ 36 阅读

相关硬币投掷实验c语言程序设计,投掷硬币（动态规划）

\1506 : 投掷硬币时间限制: 10000ms 单点时限: 1000ms 内存限制: 256MB 描述小Hi有一枚神奇的硬币。已知第i次投掷这枚硬币时，

浅浅的花香味﹌/ 2022年10月14日 13:49/ 0 赞/ 183 阅读

相关 426-动态规划算法-硬币选择问题

硬币选择问题硬币选择问题：有1，3，5分面额的硬币，给定一个面值11，问组成给定面值所需要的最少的硬币数量是多少？？？我们先用分治算法解决 ![在这里插入图片

小咪咪/ 2022年09月05日 04:24/ 0 赞/ 229 阅读

相关【动态规划】最小硬币面值组合

问题给出硬币种类，及要组合的sum，求用最少的硬币数目到达sum。如：硬币种类1,5,8 sum为20，则最少的硬币数目为5555。解析动态规划解法：

太过爱你忘了你带给我的痛/ 2022年08月09日 15:48/ 0 赞/ 224 阅读

相关【动态规划】硬币面值组合（上台阶）

问题 1分2分5分的硬币三种，组合成1角，共有多少种组合？有1分，2分，5分，10分四种硬币，每种硬币数量无限，给定n分钱，有多少中组合可以组成n分钱？

逃离我推掉我的手/ 2022年08月09日 03:16/ 0 赞/ 235 阅读

相关动态规划凑硬币

> 题目：几年教师节活动中，公司里为培训讲师提供了不同面值的饮料兑换券（每种面值数量不限），培训讲师可以领取兑换券去食堂兑换鲜榨果汁，要求兑换券和果汁必须等价，姜小虎想要兑换一

Bertha 。/ 2022年06月08日 13:35/ 0 赞/ 226 阅读

相关动态规划-硬币问题分析

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][] 什么是动态规划上次对动态规划已经有了个大概的分析

我就是我/ 2022年01月14日 14:47/ 0 赞/ 266 阅读

相关动态规划凑硬币问题

凑硬币问题假设有 1 元，3 元，5 元的硬币若干（无限），现在需要凑出 11 元，问如何组合才能使硬币的数量最少？用数组d来存储当前每个面值可以对应的合成的最小

Dear 丶/ 2021年10月01日 11:34/ 0 赞/ 443 阅读

相关模拟T次投掷硬币

一代码 package Flips; import Counter.Counter; import common.StdOut;

小灰灰/ 2021年07月24日 23:49/ 0 赞/ 336 阅读