首页 > 其他分享 >Educational DP Contest I - Coins(概率DP)

Educational DP Contest I - Coins(概率DP)

时间:2022-12-27 20:47:04浏览次数:63  
标签:Educational const 硬币 int LL Coins cin DP

https://atcoder.jp/contests/dp/tasks/dp_i

题目大意:

给定n个硬币,n是奇数,每个硬币朝上的概率是ai

问我们一半以上的硬币处于正面的概率是多少?
Sample Input 1  
3
0.30 0.60 0.80
Sample Output 1  
0.612

注意状态转移方程

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18;
const LL N=500200,M=3500;
const LL mod=1e9+7;
double a[N];
double f[M][M];//前i个硬币,有j个是正面
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    //cin>>T;
    while(T--)
    {
        LL n;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        //当只有一个硬币时只有这两种情况
        f[1][0]=(1-a[1]);
        f[1][1]=a[1];
        for(int i=2;i<=n;i++)
        {
            for(int j=0;j<=i;j++)
            {
                //没有正面的硬币时==全反
                if(j==0) f[i][j]=f[i-1][j]*(1-a[i]);
                //在前i-1个硬币时,有j-1个硬币正面,第i个硬币是正面,概率为f[i-1][j-1]*a[i];
                //在前i-1个硬币时,有j个硬币正面,第i个硬币是反面,概率为f[i-1][j]*(1-a[i]);
                else f[i][j]=f[i-1][j-1]*a[i]+f[i-1][j]*(1-a[i]);
            }
        }
        double ans=0;
        for(int i=(n+1)/2;i<=n;i++)//正的数量要比反的数量更多,n是奇数,所以是从(n+1)/2开始加
        {
            ans+=f[n][i];
        }
        printf("%.10lf\n",ans);
    }
    return 0;
}

标签:Educational,const,硬币,int,LL,Coins,cin,DP
From: https://www.cnblogs.com/Vivian-0918/p/17008952.html

相关文章

  • 一些 dp 的优化方法 Part 2
    决策单调性:分治:2D/1D决策单调性分治常见于2D/1D动态规划,其中一维是转移层数,且从一层仅转移至下一层。注意:下列讨论全部基于具有决策单调性的动态规划。四边形不......
  • DPU1.1S完全兼容FT1.1S是一颗USB2.0 HUB芯片
    DPU1.1S是一款高性能、低功耗4口高速USB2.0HUB控制器,上行端口兼容高速480MHz和全速12MHz两种模式,4个下行端口兼容高速480MHz、全速12MHz、低速1.5MHz三种模式。DP......
  • #2153. 「SCOI2005」互不侵犯(状压DP)
    #2153.「SCOI2005」互不侵犯解题思路令dp[i][j][k]表示第i行的状态为j时,共放置k个国王的方案数。状态j的二进制即表示该行的放置方式,例如j为3时,放置的方式为101,即从右......
  • 国产DP4398 兼容替代CS4398 24Bit 192KHz数模转换芯片
    CS4398是一款24Bit/192KHz规格的解码芯片,它具有120分贝以上的讯噪比和动态范围,采用一个高级专用多位Delta-Sigma调制器,并整合了失配噪声整形技术。今天来讲讲它的国产替代......
  • 解决 Ubuntu apt-get Could not get lock varlibdpkglock-frontend
    解决Ubuntuapt-getCouldnotgetlock/var/lib/dpkg/lock-frontend.E:Couldnotgetlock/var/lib/dpkg/lock-frontend.Itisheldbyprocess1927(unattended-......
  • 在 Ubuntu 22.04 上部署 WordPress
    很简单的事情被搞得很复杂,踩了很多坑……以及莫名其妙的错误。本来碰壁了之后会一拖再拖。昨天新冠阳性难受了一整天,晚上退烧了,不想学数学就想搞搞这个,第二天早上就弄好了......
  • WordPress 分页链接函数 paginate_links
    paginate_links用法<?phpechopaginate_links($args);?>paginate_links默认参数<?php$args=array('base'=>'%_%','format'=>'......
  • Mac install Php and Wordpress
     1.安装php,参考:https://kittmedia.com/en/2021/macos-install-nginx-mysql-and-php-via-brew/   [email protected]   belowisthefinishoutput:To......
  • ACM预备队-week8(DP2)
    1.疯狂的采药完全背包题目链接:P1616疯狂的采药-洛谷|计算机科学教育新生态(luogu.com.cn)1#include<bits/stdc++.h>2usingnamespacestd;3#defineint......
  • 利用WordPress搭建属于自己的网站
    怎么用WordPress给自己搭建了一个网站?可能很多人都想拥有属于自己的网站,这篇文章就找你怎么利用WordPress搭建属于自己的网站。如果你也正好有搭建个人网站的想法,那么本文......