首页 > 代码库 > uva 11021 - Tribles(概率)

uva 11021 - Tribles(概率)

题目连接:uva 11021 - Tribles

题目大意:有k只麻球,每只只活一天,临死之前可能会出生一些新的麻球,具体出生i个麻球的概率为P,给定m,求m天后麻球全部死亡的概率。

解题思路:考虑一只麻球在m天后死亡的概率为f(m) 由全概率公式有f(i)=P0+P1?f(i?1)+P2?f(i?1)2,于是考虑k只麻球,就有f(m)k

/*********************
 *
 * pi 为出生i麻球的概率
 * fi 为1只麻球在i天内死亡的概率
*********************/

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

using namespace std;
const int maxn = 1005;

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

int main () {
    int cas;
    scanf("%d", &cas);
    for (int kcas = 1; kcas <= cas; kcas++) {
        scanf("%d%d%d", &n, &k, &m);
        for (int i = 0; i < n; i++)
            scanf("%lf", &p[i]);
        f[0] = 0;
        f[1] = p[0];
        for (int i = 1; i <= m; i++) {
            f[i] = 0;
            for (int j = 0; j < n; j++)
                f[i] += p[j] * pow(f[i-1], j);
        }
        printf("Case #%d: %.7lf\n", kcas, pow(f[m], k));
    }
    return 0;
}