烟花（概率dp）

秒速五厘米 2023-01-13 15:56 147阅读 0赞

https://ac.nowcoder.com/acm/problem/18200

## 分析： ##

## double x = 1.0000 - arr\[i\];   double y = arr\[i\];   ![在这里插入图片描述][20210419150913177.png]   dp\[i\]\[j\] = p(上次没炸) + p(上次炸了)   注意不能超过k次 ##

#include<bits/stdc++.h>
    using namespace std;
    #define rep(i,a,b) for(int i=a;i<=b;++i)
    
    const int maxn = 1e5+5;
    double dp[maxn][205];
    double arr[maxn];
    
    
    int main()
    { 
        
        int n, k;
        cin >> n >> k;
        double exp = 0;
        rep(i,1,n)
        { 
            cin >> arr[i];
            exp += arr[i];
        }
        dp[0][0] = 1;
        rep(i,1,n)
        { 
           double x = 1.0000 - arr[i];
           double y = arr[i];
           rep(j,0,min(i,k)){ 
                dp[i][j] = dp[i-1][j]*x + dp[i-1][j-1]*y;
            }
        }
        printf("%.4lf\n", exp);
        printf("%.4lf", dp[n][k]);
        return 0;
    }

思路：  
https://zhuanlan.zhihu.com/p/75320558

[20210419150913177.png]: https://img-blog.csdnimg.cn/20210419150913177.png

发表评论取消回复

表情：

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

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

相关阅读

相关概率期望dp

简易的入门：http://kicd.blog.163.com/blog/static/126961911200910168335852/ 大神的总结：http://blog

港控/mmm°/ 2023年08月17日 16:25/ 0 赞/ 55 阅读

相关烟花（概率dp）

https://ac.nowcoder.com/acm/problem/18200 分析： double x = 1.0000 - arr\[i\]; doubl

秒速五厘米/ 2023年01月13日 15:56/ 0 赞/ 148 阅读

相关算法提高概率计算（概率dp）

问题描述　　生成n个∈\[a,b\]的随机整数，输出它们的和为x的概率。输入格式　　一行输入四个整数依次为n，a，b，x，用空格分隔。输出格式　　输出一行包

缺乏、安全感/ 2022年09月28日 15:20/ 0 赞/ 148 阅读

相关 POJ 3071 Football （概率DP）

POJ 3071 Football （概率DP）：[http://poj.org/problem?id=3071][http_poj.org_problem_id_3071]

绝地灬酷狼/ 2022年08月21日 11:59/ 0 赞/ 99 阅读

相关 HDU Walk （概率DP）

HDU Walk （概率DP）：[http://acm.hdu.edu.cn/showproblem.php?pid=5001][http_acm.hdu.edu.cn_sho

柔光的暖阳◎/ 2022年08月21日 11:58/ 0 赞/ 133 阅读

相关 hdu 4586 概率dp

题意：扔一个有n面的骰子，可能得到正面朝上的那个面上面的数字，有一些面比较特殊，扔到这些面上之后可能继续扔，问最终能等到的数字和的期望。分析：这道题

灰太狼/ 2022年08月20日 15:21/ 0 赞/ 122 阅读

相关 poj2096 概率dp入门

题意：一个系统有s个子系统，一共会产生n中bug。某人一天可以发现一个bug，这个bug属于一个子系统，属于一个种类，每个bug属于某个子系统的概率是1/s,属于某个分类的

我就是我/ 2022年08月20日 15:16/ 0 赞/ 123 阅读

相关 lightoj 1030 概率dp

1030 - Discovering Gold <table> <tbody> <tr> <td title="special judge"><a href

超、凢脫俗/ 2022年07月28日 04:10/ 0 赞/ 143 阅读

相关 BZOJ3566 概率充电器树形概率dp

[传送门][Link 1] 题意：给你一棵树，求能充电节点的期望个数，每条边都有一个概率，每个点也有一个概率。思路：从反面考虑：设s\[u\]是u没电，以及它的孩

不念不忘少年蓝@/ 2022年05月15日 08:00/ 0 赞/ 153 阅读

相关 CH3803 扑克牌（概率dp）

题意：Rainbow把一副扑克牌(54张)随机洗开，倒扣着放成一摞。然后Admin从上往下依次翻开每张牌，每翻开一张黑桃、红桃、梅花或者方块，就把它放到对应花色的堆里去。 R

迷南。/ 2021年11月16日 15:31/ 0 赞/ 276 阅读