链接
传送门
题意
一队\(n\)个人，单位时间队首的人有\(p\)的概率出队，求\(t\)单位时间后出队的人数量的期望。
思路
可以dp也可以使用数学二项分布公式，注意使用公式时要用对数优化精度。
代码
概率dp：
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
| #include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 2010;
double dp[maxn][maxn];
int main() {
int n, t;
double p;
scanf("%d%lf%d", &n, &p, &t);
dp[0][0] = 1;
for (int i = 0; i < t; ++i) {
for (int j = min(n - 1, i); j >= 0; --j) {
dp[i + 1][j] += dp[i][j] * (1 - p);
dp[i + 1][j + 1] += dp[i][j] * p;
}
dp[i + 1][n] += dp[i][n];
}
double ans = 0;
for (int i = 0; i <= n; ++i) {
ans += dp[t][i] * i;
}
printf("%.10f", ans);
return 0;
}
|
数学公式：
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
| #include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn = 2010;
long double Log[maxn];
int main() {
int n, t;
double p, ans = 0;
scanf("%d%lf%d", &n, &p, &t);
if (p == 1) {
ans = min(n, t);
} else if (p != 0) {
for (int i = 1; i < maxn; ++i) {
Log[i] = Log[i - 1] + log(i);
}
for (int i = 0; i <= t; ++i) {
long double tmp = Log[t] - Log[t - i] - Log[i];
tmp += i * log(p);
tmp += (t - i) * log(1 - p);
ans += min(i, n) * exp(tmp);
}
}
printf("%.10f", ans);
return 0;
}
|