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

点击量：201

    式子简单的概率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;
}