牛客 180B 烟花 题解【概率期望】【DP】【滚动数组】

作者: wjyyy 分类: DP,概率期望,滚动数组,解题报告 发布时间: 2018-09-08 07:12

点击量:15

 

    式子简单的概率DP(算递推吧)

题目描述

小a有\(n\)个烟花,每个烟花代表着互不相同的颜色,对于第\(i\)个烟花,它有\(p_i\)的概率点燃,现在小a要去点燃它们,他想知道产生颜色的期望个数及产生恰好产生\(k\)种颜色的概率。

输入描述:

第一行两个整数\(n,k\),

接下来一行\(n\)个数,第\(i\)个数\(p_i\)表示第\(i\)个烟花被点燃的概率。

输出描述:

输出有两行。

第一行表示产生不同颜色的期望个数,第二行表示产生恰好种颜色的概率。以换行符分割。

输入输出样例

输入样例#1:

3 2
0.5 0.25 0.75

输出样例#1:

1.5000
0.4063

说明

第二问样例解释:

\((1,2):0.5\times 0.25\times (1-0.75)=0.03125\)

\((1,3):0.5\times (1-0.25)\times 0.75=0.28125\)

\((2,3):(1-0.5)\times 0.25\times 0.75=0.09375\)

相加得\(0.40625\)。

对于\(30\%\)的数据:\(n\le 6,k\le n\),

对于\(100\%\)的数据:\(n\le 10^5,k\le 2\times 10^2\)。

输出均保留4位小数,若你的答案误差与std不超过\(10^{-4}\)即为正确。

题解:

    产生颜色的期望就按照期望的定义来,就是\(\sum p_i\),因为每个烟花能产生的颜色只有1种,而我们需要关注的是第二问。

    首先看样例解释,找不到组合数的规律,因为一个元素在一个组合中出现时,既有可能是\(p_i\),又有可能是\(1-p_i\),所以不能直接乘上\(C_n^k\)。同时,对于\(C_n^k\)也没有合适的分母,如果没有分母,这个概率值是很有可能超过1的。

    但是如果把烟花一个一个拆开来看,可以发现它是有阶段性的。也就是一个烟花有\(p_i\)的概率爆炸,把原有的颜色数\(+1\),有\((1-p_i)\)的概率不爆炸,不增加原有的颜色数。这一阶段的概率就保证为\(1\)了,满足概率的转移性质。

    因此考虑用f[i][j]表示前\(i\)个烟花中爆炸\(j\)个的概率。那么状态转移方程为f[i][j]=p[i]*f[i-1][j-1]+(1-p[i])*f[i-1][j],注意枚举\(j\)的范围,小心时间复杂度。但是这样空间复杂度不对,而我们发现f[i]阶段只能由f[i-1]阶段转移,因此可以用滚动数组优化。

    但是状态转移方程写成f[i][j]=p[i]*f[i-1][j]+(1-p[i])*f[i-1][j-1]也是对的,不知道是什么玄学。

Code:

#include<cstdio>
#include<cstring>
double f[2][222];
double p[100100];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        scanf("%lf",&p[i]);
        p[0]+=p[i];
    }
    printf("%.4lf\n",p[0]);//第一问直接输出概率和
    f[0][0]=1.0;
    for(int i=1;i<=n;++i)
    {
        f[i&1][0]=f[(i&1)^1][0]*(1-p[i]);//0没有j-1,所以要特判
        for(int j=1;j<=n&&j<=m;++j)
            f[i&1][j]=f[(i&1)^1][j]*(1-p[i])+f[(i&1)^1][j-1]*p[i];
    }
    printf("%.4lf\n",f[n&1][m]);
    return 0;
}

说点什么

avatar
  Subscribe  
提醒
/* */