UVA11021 Trible

UVA11021 Tribles

题目大意

一开始有 k 种生物，这种生物只能活1天，死的时候有 $p_i$的概率产生 i 只这种生物（也只能活一天），询问m天内所有生物都死的概率（包括m天前死亡的情况）

solution

概率DP水题 如果不会概率与期望的可以到我的博客my blog中查看。

显然对于每个生物m天全挂掉的概率一样，于是我们就只用考虑其中一只，另dp[i]为一只生物在i天后死掉的概率。

由全概率公式dp[i]=$sum_{j=0}^{n-1}p[j]*dp[i-1]^j$


代码如下

#include<bits/stdc++.h>

using namespace std;

const int MAXN  = 1000+10;

inline int read()
{
    int f=1,x=0;
    char ch;
    do
    {
        ch=getchar();
        if(ch=='-') f=-1;
    }while(ch<'0'||ch>'9');
    do
    {
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }while(ch>='0'&&ch<='9');
    return f*x;
}

int t;
int n,m,k;
double dp[MAXN];
double p[MAXN];
int num=0;

int main()
{
    t=read();
    while(t--)
    {
        n=read();k=read();m=read();
        for(int i=0;i<n;i++) scanf("%lf",&p[i]);
        dp[0]=0;dp[1]=p[0];
        double sum;
        for(int i=2;i<=m;i++) 
        {
            sum=1;
            dp[i]=0;
            for(int j=0;j<n;j++)
            {
                dp[i]+=p[j]*sum;
                sum*=dp[i-1];   
            }
        }
        ++num;
        printf("Case #%d: %.7f
",num,pow(dp[m],k));
    }
}