UVA-11021-Tribles-概率问题 | 李博的博客
0%

UVA-11021-Tribles-概率问题

有 $k$ 只麻球,每只活一天就会死亡,临死前可能会生出一些新的麻球。具体来说,生 $i$ 只麻球的概率为 $p_i$ 。给定 $m$ ,求 $m$ 天后所有麻球均死亡的概率。

每只麻球均可视为一个独立的问题。设 $f[i]$ 表示:第一天只有 $1$ 只麻球,在第 $i$ 天它及它的后代全部死亡的概率。由全概率公式,有递推公式:
$$
\begin{eqnarray}
f[i]&=&P_0+P_1f[i−1]+P_2f[i−1]^2+P_3f[i−1]^3+ \cdots +P_{n−1}f[i−1]^{n−1} \\
&=&\sum_{j=0}^{n-1}{P_jf[i-1]^j}
\end{eqnarray}
$$
其中 $P_jf[i−1]^j$ 的含义是这个麻球生了 $j$ 个后代,并且它们在 $i−1$ 天后全部死亡的概率。由于一开始有 $k$ 只麻球,最终答案为 $f[m]^k$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <cstring>
#include <map>
#include <algorithm>
#include <vector>
#include <queue>
#include <iostream>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <climits>
#include <cmath>
#define LL long long
using namespace std;
const int maxn = 1000 + 10;
double f[maxn], P[maxn];
int n, k, m;
int main(){
int T; scanf("%d", &T);
for(int Case = 1; Case <= T; Case++){
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 = 2; 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", Case, pow(f[m],k));
}
return 0;
}
如果对您有帮助,请我喝杯奶茶?