题意:有k只 Tribles ,每一只Trible可以恰好活一天,第二天会死,死的时候生下一些小Tribles,每只小Trible继续活和生仔。现在要知道第m天时没有Trible的概率是多少。已知每一只Trible产下的小Trible的数量为[0,n-1],概率分别为$P_0,P_1,*,P_{n-1}$,也就是产下i只的概率为$P_i$(m,n,k∈[0,1000],有多组数据)

思路:很自然地想到用f[i][j]表示第i天有j只Trible地概率,递推即可。问题是对于每个状态我们又要花O(m)转移,所以绝对行不通。

那么如果直接用f[i]表示第i天没有Trible的概率呢?其实可以。首先明确一个事实:我们只需要知道对于1只Trible的f[i],答案最后取k次幂即可。现在如果要求第i天没有Trible的概率,那么首先你得让第一只Trible生的孩子死光,那么就是$f[i-1]^x$,其中x为生的数量(每一只都得死,所以是x只的概率乘起来)。所以得出一个优美的公式

\begin{equation}
f[i]=\sum_{i=0}^{n-1}{P_i*f[i-1]^i}
\end{equation}

这样就可以在O(nm)的复杂度内求解啦!

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>

#define MX 1005

using namespace std;

int n,k,m;
double p[MX],f[MX];

void input()
{
    scanf("%d%d%d",&n,&k,&m);
    for(int i=0;i<=n-1;i++)scanf("%lf",&p[i]);
}

int main()
{
    int t;
    scanf("%d",&t);
    for(int w=1;w<=t;w++)
    {
        input();
        memset(f,0,sizeof(f));
        for(int i=1;i<=m;i++)
            for(int j=0;j<=n-1;j++)
                f[i]+=pow((double)f[i-1],j)*p[j];
        printf("Case #%d: %.7f\n",w,pow(f[m],k));
    }
    return 0;
}
分类: 文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *