Codeforces 518D Ilya and Escalator

链接

传送门

题意

一队$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;
}

支付宝扫码领红包