UVa 11021 (概率 递推) Tribles

Tribble是麻球？

因为事件都是互相独立的，所以只考虑一只麻球。

设f(i)表示一只麻球i天后它以及后代全部死亡的概率，根据全概率公式：

f(i) = P0 + P1 * f(i-1) + P2 * f(i-1) + ... + Pn * f(n)

每个麻球死亡是独立的，所以Pj * f(i-1) 表示生了j个麻球，这j个麻球要在i-1天内全部死亡。

 #include <cstdio>

 #include <cmath>

 using namespace std;

 const int maxn =  + ;

 double f[maxn], p[maxn];

 int main()

 {

     //freopen("in.txt", "r", stdin);

     int T;

     scanf("%d", &T);

     for(int kase = ; kase <= T; kase++)

     {

         int n, k, m;

         scanf("%d%d%d", &n, &k, &m);

         for(int i = ; i < n; i++) scanf("%lf", &p[i]);

         f[] = ;

         f[] = p[];

         for(int i = ; i <= m; i++)

         {

             f[i] = ;

             for(int j = ; j < n; j++) f[i] += p[j] * pow(f[i-], j);

         }

         printf("Case #%d: %.7f\n", kase, pow(f[m], k));

     }

     return ;

 }

代码君