首页 > 其他分享 >抛硬币(概率dp)

抛硬币(概率dp)

时间:2024-08-16 21:15:57浏览次数:15  
标签:概率 硬币 int 正面 dp 朝上

https://www.luogu.com.cn/problem/AT_dp_i 第1题     抛硬币 查看测评数据信息

有n个质地不均匀的硬币,抛第i枚硬币器正面朝上的概率是p[i],反面朝上的概率是1-p[i],扔完n个硬币后,求正面朝上的个数大于反面朝上的概率是多少。结果保留三位小数

输入格式

 

第一行一个整数n,表示有n枚硬币

第二行n个实数,表示第i个数的正面朝上的概率

1<=n<=2999,0<p[i]<1

 

输出格式

 

一个实数

 

输入/输出例子1

输入:

3

0.30 0.60 0.80

 

输出:

0.612

 

输入/输出例子2

输入:

1

0.50

 

输出:

0.500

 

样例解释

 

 

 

看到概率,就往dp方面想

写dp前可以先看范围

 

这题O(n^2),不难想到第一维肯定是对于前i个硬币。

状态要转个弯,直接求正面>反面比较难算,我们可以求出正面数量,用n-正面得出反面,就可以比较了

状态就出来了,f[i][j]: 考虑前i个硬币,有j个正面朝上的概率

 

转移:按照第i个硬币正反讨论:
1.正: f[i-1][j-1]*p[i]
2.反: f[i-1][j]*(1-p[i])

 

答案:
f[n,n/2+1~n]

 

这题类似背包,就是选和不选

#include <bits/stdc++.h>
using namespace std;
const int N=3010;

int n;
double a[N], f[N][N], ans=0;
int main()
{
	scanf("%d", &n);
	for (int i=1; i<=n; i++) scanf("%lf", &a[i]);
	
	f[0][0]=1;
	for (int i=1; i<=n; i++)
		for (int j=0; j<=i; j++)
		{
			if (j>=1) f[i][j]=f[i-1][j-1]*a[i];
			f[i][j]+=f[i-1][j]*(1.0-a[i]);
		}
			
/*	
	for (int i=1; i<=n; i++)
	{
		for (int j=1; j<=i; j++) printf("%.3lf ", f[i][j]);
		printf("\n");
	}*/
		
	for (int i=n/2+1; i<=n; i++) ans+=f[n][i];
	printf("%.3lf", ans);
	return 0;
}

  

 

 

 

标签:概率,硬币,int,正面,dp,朝上
From: https://www.cnblogs.com/didiao233/p/18363640

相关文章

  • 第六章 网络互连与互联网(五):TCP 和 UDP 协议
    五、TCP和UDP协议在TCP/IP协议簇中有两个传输协议,即传输控制协议(TCP)和用户数据报协议(UDP)。TCP是面向连接的,而UDP是无连接的。1、TCP服务(1)TCP协议提供面向连接的、可靠的传输服务,适用于各种可靠的或不可靠的网络。(2)TCP用户送来的是字节流形式的数据,这些数据缓存......
  • 力扣 | 一维简单线性dp | 2140. 解决智力问题、322. 零钱兑换、2466. 统计构造好字符
    文章目录一、2140.解决智力问题二、322.零钱兑换三、2466.统计构造好字符串的方案数四、91.解码方法五、983.最低票价六、790.多米诺和托米诺平铺需要特别注意的题目有2140.解决智力问题和983.最低票价,因为这两个题目可以启发思路,其他的题都比较普通。一、21......
  • Python 通过UDP传输超过64k的信息
    在UDP中,单个数据包的最大尺寸通常受到网络层的限制,这通常被称为最大传输单元(MTU)。在以太网环境中,标准的MTU大小通常为1500字节。尽管有些网络环境可能支持更大的数据包,但是UDP数据包的理论最大限制是65535字节(64KB),这是由于UDP头部的16位长度字段决定的。然而,如果你需要发送超过这......
  • P4290 [HAOI2008] 玩具取名(区间dp,传递闭包?)
    link有点传递闭包的思想感觉这题(无聊倒装首先为了便于处理,将W,I,N,G映射为1,2,3,4那么处理数据,想到可以用传递闭包的思想?感觉差不多,因为这道题有很多一一对应的关系对于每次输入对应的两个字符\(ab\),定义\(g[a,b,i]\in\{0,1\}\)表示对应关系题目要求给定一个串\(s\)......
  • 初识DPDK
    DPDK是dataplanedevelopmekit的缩写,是一个c语言编写的软件开发框架,常用于高性能网络的开发。它的主要功能就是让用户绕过linux内核协议栈,将网卡收到的数据包直接在用户态空间内使用用户自定义的逻辑去处理数据包,或者将用户态空间的数据包绕过一系列的内核协议栈封装直接从网卡......
  • 2024.8.14 DP Round 2
    A.storeStatement:有\(n(1\len\le100)\)个果盘,其中第\(i\)个果盘有\(a_i\)个水果,容量是\(b_i(a_i\leb_i\le100)\)。一次操作可以将一个水果从一个果盘放到另一个果盘中,现在要将所有水果放到最少的盘子中,问最少要用多少盘子以及最少需要多少操作。Solution:第一......
  • 亮相2024 DPU&AI Networking创新大会,天翼云斩获两项大奖!
    近日,以“智驱网络芯动未来”为主题的2024DPU&AINetworking创新大会在北京举办。大会表彰了在DPU与AI网络技术创新及实践应用中取得卓越成就的单位与项目,天翼云科技有限公司荣膺创新引擎奖、《紫金DPU算力卸载与网络加速应用》荣获实践先锋奖,技术创新实力以及应用实践成果再获行......
  • udp和arp之间的交互作用
    udp和arp之间的交互作用arp-a验证arp告诉缓存是空的sock-u-i-nl-w8192svr4discard1.在第一个arp应答返回以前,总共产生了6个arp请求。2.在接收到第一个arp应答时(第7行),只发送最后一个数据报片(第9行)3.在大多数的现实中,在等待一个arp应答时,只将最后一个报文发送给特定目标......
  • udp介绍
    1.udp介绍udp是一个简单的面向数据报的运输层协议,进程的每个输出操作都正好产生一个udp数据报,并组装成一份待发送的ip数据包,这与面向流字符的协议不同,如tcp,应用程序产生的全体数据与真正发送的单个ip数据报可能没有什么联系。udp不提供可靠性:它把应用程序传给ip层的数据发送出......
  • 「Day 9 & 10—DP问题」
    DP问题定义什么是\(DP\),答曰:一种通过将全局问题分解成不同的子问题来进行对复杂问题的计算。在我看来就是一种递推的\(ProMax\)版,依旧是用之前计算过的来推出现在要计算的。DP板子问题P1115最大子段和思路我们用\(dp\)数组来定义到\(i\)为止,最大的子段和,那么我们......