Atcoder dp I Coins 题解

Atcoder链接:Coins

Luogu链接:Coins


$\scr{\color{BlueViolet}{Solution}}$

观察数据,发现$ \cal{n} \le 3000 $,说明 $ Ο(\cal{n^2}) $可过,容易想到DP。

用 $\cal{dp[i][j]}$ 表示抛完第$\cal{i}$个硬币时,有$\cal{j}$个硬币正面朝上的概率。

 考虑$\cal{dp[i][j]}$如何转移,易发现有以下两种情况,(当前正面朝上概率为 $\cal{p_i}$):

  • 本次抛得硬币是正面:抛到正面概率 乘 抛完第$\cal{i-1}$个硬币后,有$j-1$个硬币朝上的概率。
  • 本次抛得硬币是反面:抛到反面概率 乘 抛完第$\cal{i-1}$个硬币后,有$j$个硬币朝上的概率。

我们把以上两种情况表示出来,也就是:${dp[i][j]} = {p_i}  \times {dp[i-1][j-1]} + {1-p_i} \times {dp[i-1][j]}$

初始值:$\cal{dp[0][0]=1}$,因为第$0$次抽到$0$张卡的概率一定是$1$。

其余$dp[i][j]$值都为0。

然后就好了,最后统计一下符合条件的所有可能情况。

时间复杂度:$\cal{O(n^2)}$

Code:

#include<bits/stdc++.h>
#define L long long
using namespace std;
double a[3005];
double dp[3005][3005];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lf",&a[i]);
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=i;j++)
        {
            if(i==j) dp[i][j]+=dp[i-1][j-1]*a[i];
            else if(j!=0) dp[i][j]+=dp[i-1][j-1]*a[i]+dp[i-1][j]*(1-a[i]);
            else dp[i][j]+=dp[i-1][j]*(1-a[i]);
        }
    }
    double summ=0;
    for(int i=1;i<=n;i++)
    if(i>n-i) summ+=dp[n][i];
    printf("%.9lf",summ);
    return 0;
}

 

本文转载于网络 如有侵权请联系删除

相关文章

  • CV未来,路在何方?李飞飞指路!

    【导读】ImageNet见证了计算机视觉发展的辉煌历程,在部分任务性能已超越人类的情况下,计算机视觉的未来又该如何发展?李飞飞最近发文指了三个方向:具身智能,视觉推理和场景理解。在深度学习革命进程中,计算机视觉依托大规模数据集ImageNet,在图像分类、目标检测、图像生成等多个任务都表现出惊人的性能,甚至比人类的准确率还要高!但CV为何能取得如此巨大的成就?未来将向何处发展?最近,「华人AI女神」李飞飞在美国文理科学院的会刊Dædalus上发表了一篇文章,以计算机视觉中的物体识别任务为切入点,研究了ImageNet数据集及相关算法的发展历程。文章链接:https://www.amacad.org/publication/searching-computer-vision-north-stars文章认为技术的发展很大程度上源于对北极星(NorthStars)的追求。「北极星」在这里指的是研究人员专注于解决一个科学学科中的关键问题,可以激发研究热情并取得突破性的进展。在ImageNet和物体识别的成功之后,越来越多的北极星问题涌现出来。这篇文章主要讲述了ImageNet的简要历史、其相关

  • write函数的详解与read函数的详解[通俗易懂]

    大家好,又见面了,我是你们的朋友全栈君。write()头文件:#include<unistd.h>复制原型:ssize_twrite(intfd,constvoid*buf,size_tcount); 参数说明: fd:是文件描述符(write所对应的是写,即就是1) buf:通常是一个字符串,需要写入的字符串 count:是每次写入的字节数复制返回值:成功:返回写入的字节数 失败:返回-1并设置errno ps:写常规文件时,write的返回值通常等于请求写的字节 数count,而向终端设备或者网络写时则不一定复制read()头文件:#include<unistd.h> 功能:用于从文件描述符对应的文件读取数据(从打开的设备或文件中读取数据)复制原型:ssize_tread(intfd,void*buf,size_tcount) 参数说明: fd:是文件描述符 buf:为读出数据的缓冲区; count:为每次读取的字节数(是请求读取的字节数,读上来的数据保 存在缓冲区buf中,同时文件的当前读写位置向后移)复制返回值:成功:返回读出的字节数 失败:返回-1,并

  • 腾讯云服务器按带宽计费与使用流量计费有什么区别?如何选择?

    腾讯云服务器计费标准其中一项就是宽带计费,计费模式有按带宽计费与使用流量两种,那么这两种计费模式有什么区别?在购买时应该如何选择是很多新手用户都想了解的问题,下面腾讯云优惠网来详细解读一下按带宽计费与使用流量计费。腾讯云服务器cvm.jpg注:购买腾讯云服务器可先领取2860元腾讯云代金券,最低可获得受满200减100,最高可获得满2000减1000优惠。一、腾讯云服务器是否限制流量?腾讯云服务器有流量限制吗?很多新手用户都会问这个问题。其实云服务器限制的是带宽,自定义购买时可以选择按使用量计费,此时宽带最高可设定为200M,但流量会单独计费,约0.8元/GB。只要余额充足,就不会限制流量。但是如果选择的是轻量应用服务器是有流量限制的,轻量应用服务器一般是根据配置的高低来决定流量限制的大小,例如轻量应用服务器特惠活动中,2核CPU2GB内存4Mbps带宽的流量限制为300GB/月,2核CPU4GB内存6Mbps带宽的流量限制为1000GB/月。二、固网宽带和按流量计费的解读公网带宽支持固定带宽计费和流量计费区别按带宽计费腾讯云根据用户云服务器公网出带宽计费,计费单位为Mbps。特点:固

  • 【小Y学算法】⚡️每日LeetCode打卡⚡️——42. 相交链表

    ????前言????原题样例:相交链表????C#方法:深度优先搜索????Java方法一:哈希集合????Java方法二:双指针????总结????前言????算法题????????每天打卡一道算法题,既是一个学习过程,又是一个分享的过程????????提示:本专栏解题编程语言一律使用C#和Java两种进行解题????要保持一个每天都在学习的状态,让我们一起努力成为算法大神吧????!????今天是力扣算法题持续打卡第42天????!????算法题????????原题样例:相交链表给你两个单链表的头节点headA和headB,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回null。图示两个链表在节点c1开始相交: 题目数据保证整个链式结构中不存在环。注意,函数返回结果后,链表必须保持其原始结构。实例1 输入:intersectVal=8,listA=[4,1,8,4,5],listB=[5,0,1,8,4,5],skipA=2,skipB=3 输出:Intersectedat'8' 解释:相交节点的值为8(注意,如果两个链表相交则不能为0)。

  • 如何做好大型遗留系统的数据迁移

    历史悠久的大型企业,都会存在遗留系统。这些系统运转着重要的业务,但使用到的技术已经跟不上时代潮流。因此有着维护成本高、难以扩展、用户体验差等缺陷。最终,企业一定会下决心开发一套全新的系统来替代遗留系统。除了完成新系统的开发,还有一项重要的工作,是将老系统中存留的数据迁移进新系统,也就是我们常说的数据迁移。如果你没有数据迁移的经验,很容易低估其难度。数据迁移看起来只是把数据从一个DB转移到另外一个DB,select+insert+转换逻辑就可以轻松搞定。如果带着这个想法开始数据迁移项目,你的团队很快就会坠入深渊,举步维艰。数据迁移是一项看似简单,实而复杂且繁琐的工作,想要做好并不容易。为什么数据迁移项目难做 不久前,我刚刚完成一次数据迁移项目。虽然项目结果很成功,但过程中遇到很多开始之初没有想到的问题,导致项目过程非常痛苦。如果在项目开始时就把这些问题考虑进来,过程会轻松很多,风险也会小很多。下面我们来看看数据迁移项目所面临的挑战有哪些。陌生的遗留系统DB设计作为新系统的开发方,你一定熟知新系统的DB设计。但是遗留系统的DB设计想必你一定不甚了解。作为要被替换的遗留系统,其开发方肯定也不

  • PYTHON实现swf提取

    #!/usr/bin/envpython #coding=utf-8 importsys,os##参数处理forwindows,和操作系统交互 importre##正则表达式处理工具 importstruct##二进制数据操作 defextract_swf(filename,buf,offset): try: length=struct.unpack_from('<L',buf,offset+4)[0] swfname=filename+'_offset_0x%x.swf='%offset open(swfname,'wb').write(buf[offset:offset+length]) print'[+]Findembededswffileatoffset0x%x'%offset print'[+]Saveembededswffileto'+swfname except: pass defusage(): print'Usage:extract_swf.py

  • 契约测试

    系统的服务化、前后端分离等等开发模式和技术系统⼯工程中服务依赖的复杂度在成指数级增⻓长系统的可靠性等于各个依赖服务的可靠性的乘积也就是说:A服务的可靠性是99%,B服务的可靠性是99%,C服务的可靠性是99%,如果⼀一个系统需要A调⽤用B,B调⽤用C,那么这个系统的可靠性=0.99*0.99*0.99=0.9702契约是规定得到多⽅方承认、信守的内容契约测试是验证服务的Provider是否按照期望的⽅方式与服务的Consumer进⾏行行交互,简单的说是Consumer与Provider两者之间的集成。契约测试是以消费者提出接⼝口契约,交由服务提供⽅方实现,并以测试⽤用例例对契约进⾏行行产⽣生约束,所以服务提供⽅方在满⾜足测试⽤用例例的情况下可以⾃自⾏行行更更改接⼝口或架构实现⽽而不不影响消费者。契约测试是⼀一种针对外部服务的接⼝口进⾏行行的测试,它能够验证服务是否满⾜足消费⽅方期待的契约。它的本质是从利利益相关者的⽬目标和动机出发,最⼤大限度地满⾜足需求⽅方的业务价值实现。

  • 跑鞋的春天?阿迪达斯发布Futurecraft 4D款3D打印跑鞋

    阿迪达斯与硅谷新创公司Carbon达成合作,采用最新3D打印技术DigitalLightSynthesis打造鞋子。早前,阿迪达斯已经采用了3D技术打造鞋子,但还只是小批量的供应。为了增加3D打印鞋子的供应量,阿迪达斯这次与硅谷新创公司Carbon达成合作,克服了3D打印速度慢的问题,引入了最新的3D打印技术“DigitalLightSynthesis”。目前,阿迪达斯打印一双Futurecraft4D运动鞋需要一个半小时,在未来则有望缩短至20分钟,从而大大提升产能。这是全球第一双采用“光和氧气”打造中底的鞋款,新的DigitalLightSynthesis技术采用透氧光学、数字光投射和可编程液体树脂来制造鞋底,可以打造符合每个人足部运动、缓震、稳定和舒适偏好的专属大底,同时还可以令产品更耐用。另外,阿迪达斯还融入了其17年的跑步数据,确保其性能表现优异。有了DigitalLightSynthesis技术的帮忙,阿迪达斯在鞋子方面的迭代也可以加速进行,以往需要35天的时间,而现在只需要2到3天的时间。阿迪达斯希望,在未来,普通消费者只需邮寄个人资料就可以让阿迪达斯打造符合自己需求的完

  • 学界 | 超越ImageNet:谷歌内建300M图像数据集揭露精度与数据的线性增长关系

    F选自GoogleResearch机器之心编译参与:蒋思源、路雪自残差网络以来,深度模型拥有了极大的容量,同时GPU、TPU等硬件为深度学习提供了巨大的计算力。但计算机视觉最主要的数据集还是仅拥有1M图片的ImageNet,因此谷歌希望利用300M的大数据集进一步检验模型的能力和提升空间。过去十年,计算视觉领域取得了巨大成就,其中许多成果应归功于深度学习模型在该领域的应用。自2012年起,这些系统的能力取得了极大的进步,这应归功于(a)模型复杂度更高,(b)持续增强的计算力,(c)拥有大量标注数据。但是,尽管计算能力和模型复杂度每年都在提升(从7层的AlexNet到101层的ResNet),但可使用的数据集并未随之增加。101层的ResNet比AlexNet的容量(神经网络深度)大得多,但是仍然只能使用从ImageNetcirca2011获取的1M图像。作为研究者,我们一直在思考:如果训练数据扩展到原来的10倍,正确率是否会大量提升?100倍或者300倍呢?正确率停滞不前,还是更多的数据将带来更多的成果?过去五年中,GPU计算力和模型大小持续增加,但是最大训练数据集的大小却保持不变。

  • 可以添加自定义的Select控件

    1.控件dom<selectname="WebSiteTarget"id="WebSiteTarget"class="w1"onchange="editable2(this);"> <optionvalue="-1">请选择城市</option> <option>福州</option> <option>厦门</option> <option>南平</option> <optionvalue="0">(自定义输入)</option> </select>复制2.脚本<script> functioneditable2(dom){ if(dom.value=="0"){ varnewvalue=prompt("请输入",""); if(newvalue){ ad

  • mysql中exists的用法详解[通俗易懂]

    大家好,又见面了,我是你们的朋友全栈君。前言在日常开发中,用mysql进行查询的时候,有一个比较少见的关键词exists,我们今天来学习了解一下这个 exists这个sql关键词的用法,这样在工作中遇到一些特定的业务场景就可以有更加多样化的解决方案语法解释语法SELECTcolumn1FROMt1WHERE[conditions]andEXISTS(SELECT*FROMt2);说明括号中的子查询并不会返回具体的查询到的数据,只是会返回true或者false,如果外层sql的字段在子查询中存在则返回true,不存在则返回false即使子查询的查询结果是null,只要是对应的字段是存在的,子查询中则返回true,下面有具体的例子执行过程1、首先进行外层查询,在表t1中查询满足条件的column1 2、接下来进行内层查询,将满足条件的column1带入内层的表t2中进行查询, 3、如果内层的表t2满足查询条件,则返回true,该条数据保留 4、如果内层的表t2不满足查询条件,则返回false,则删除该条数据 5、最终将外层的所有满足条件的数据进行返回使用案例环境准备?mysql版本:8.0

  • from Crypto.Util.py3compat import byte_string ImportError: cannot import name &#39;byte_string&#39;

    #重新安装一下依赖包就可以了 pip3uninstallpycrypto pip3uninstallpycryptodome pip3installpycryptodome复制  

  • Map接口的实现类

    HashMap HashMap源码阅读 LinkedHashMap LinkedHashMap是HashMap的子类,实际上它连HashMap的putVal等方法都没有重写,因为HashMap就调用了预留给子类的函数,在HashMap中是空实现,在LinkedHashMap中重写,用作建立双向链表 staticclassEntry<K,V>extendsHashMap.Node<K,V>{ Entry<K,V>before,after; Entry(inthash,Kkey,Vvalue,Node<K,V>next){ super(hash,key,value,next); } } 复制 这是LinkedHashMap中的一个类,结合上方信息可看出,LinkedHashMap并没有修改HashMap的数据结构,只是在HashMap的基础上添加了两个元素 newNode方法是putVal中调用的,生成节点的方法,在linkedHashMap也被重写了 Node<K,V>newNode(inthash,Kkey,Vvalue,N

  • apt-get update时卡在 waiting for headers

    apt-getupdate时卡在waitingforheaders,等了好久,最后报出HashSummismatch的错误解决方法:rm/var/lib/apt/lists/*rm/var/lib/apt/lists/partial/*apt-getupdate

  • 如何给HashMap设置初始化容量

      在脉脉上看到一个帖子,大致是说,leader的代码在创建HashMap对象时,会主动设置初始容量大小,不知道这么操作到底对不对。     是否需要设置初始容量 答案是:如有必要,尽量设置。 为什么?因为随着元素的增加,Map会进行多次resize(扩容),影响性能。假如我们已经知道要添加的元素数量,创建Map对象就将容量设置到位,就可避免resize操作。 这也是阿里的Java开发手册中,明确推荐“集合初始化时,指定集合初始值大小”。并且推荐设置初始容量为initialCapacity=(需要存储的元素个数/负载因子)+1。      如何设置初始容量 根据阿里开发手册的推荐,初始容量设置为initialCapacity=(需要存储的元素个数/负载因子)+1,为何要如此设置呢? 如帖子中所说 比如给mybatis传5个参,就newHashMap<>(5) 在创建对象时,会将实际的容量值,设置为比该容量值(5)大且最接近的2的幂(也就是8)。 在添加元素时,当元素个数大于容量阈值(容量阈值=容量值*负载因

  • Linux下MySQL的数据文件存放在哪里的?

    mysql>showvariableslike'%dir%';

  • 权限修饰符

    权限修饰符 public>protected>不写>private public:同一个模块都能访问 protected:同一模块不同包只能继承关系下能访问 不写:在同一个包下可以访问 private:同一个类中可以访问 复制 同一个类中 同一个包不同类中 不同包有继承关系 不同包无关类 public √ √ √ √ protected √ √ √ 不写 √ √ private √

  • 细数Python Flask微信公众号开发中遇到的那些坑

    最近两三个月的时间,断断续续边学边做完成了一个微信公众号页面的开发工作。这是一个快递系统,主要功能有用户管理、寄收件地址管理、用户下单,订单管理,订单查询及一些宣传页面等。本文主要细数下开发过程中遇到的各种坑,也算是另外一种总结吧。 1.开发语言及框架 Python+Flask+Bootstrap,数据库使用的是MySQL   2.相关文档及Lib库 1)Bootstrap官方文档http://v3.bootcss.com/getting-started/ 2)微信公众号开发文档https://mp.weixin.qq.com/wiki 3)Python微信SDKhttps://github.com/zwczou/weixin-python/ 4)PDF《FlaskWeb开发:基于Python的Web应用开发实战》 3.那些坑 3.1微信 3.1.1微信登陆 首先你需要仔细阅读官方文档,简单来说微信登陆有如下几步: 1)生成微信认证跳转URL,注意有`snsapi_base`跟`snsapi_userinfo`两种方式,前者是静默授权只获取用户openid,后者需要用户手动同

  • Codeforces Round #512 E - Vasya and Good Sequences

    有时候觉得自己就是个思路搬运机,只会搬运思路   这个题首先说了求的是好区间的个数, 好区间满足条件:1、二进制位1的数量和为偶数  2、w[i]表示a[i]的二进制上1的个数,sum[i]=w[1]+...+w[i],对于l-r区间上任意一个位置j,w[j]<sum[r]-sum[l]-w[j]   设置一个dp[n][2]数组,dp[i][0]代表   以i为结尾的,区间内二进制1的个数和为偶数的  区间个数           dp[i][1]代表   以i为结尾的,区间内二进制1的个数和为奇数的  区间个数   然后再用dp[i][0] - 所有不满足条件2的区间,把所有满足的区间求和即可   这个1<=a[i]<=1e8 1e8比这个longlong要小,60二进制位就可以保存,  所以这个 l-r 这个区间 &

  • python科学计算包安装

    因需要,不使用Anaconda,重新安装Numpy,Scipy,Matplotlib. 1.下载.whl包在下面的网站中找需要的.whl文件下载http://www.lfd.uci.edu/~gohlke/pythonlibs/本机环境python3.6 numpy-1.13.3+mkl-cp36-cp36m-win_amd64 scipy-0.19.1-cp36-cp36m-win_amd64 matplotlib省略   直接用离线包下载没有出错。另外,安装的时间如果出现文件拒绝访问可能是打开了某些PYTHON的IDE,将IDE关闭即可  

  • [华为oj]公共子串计算

    照旧,先上下我的暴力破解法: #include<iostream> #include<string> #include<algorithm> usingnamespacestd; stringToLower(stringss) { string::iteratoritr; for(itr=ss.begin();itr!=ss.end();itr++) { *itr=tolower(*itr); } returnss; } intgetCommonStrLength(stringpFirstStr,stringpSecondStr) { intfirstLen=pFirstStr.length(); intsecondLen=pSecondStr.length(); intcountMax=0; for(intf=0;f<firstLen;f++) { intfCurrent=f; for(ints=0;s<secondLen;s++) { inttempCount=0; intsCurrent=s; while(sCurrent

相关推荐

推荐阅读