Codeforces 518D(概率期望DP)

Codeforces 518D
题意:有$n$个人,每秒有$p$的概率有一个人进电梯,问$t$秒后电梯里的人数的期望。

设$dp(i,j)$为前$i$秒进$j$个人的概率。则
$$dp(i,j)=dp(i - 1, j - 1) \cdot p + dp(i - 1, j) \cdot (1 - p)$$
但是如果$j=n$,则
$$dp(i,j)=dp(i - 1, j - 1) \cdot p + dp(i - 1, j)$$
因为这样可以继承之前的值。如果没有人数限制,就可以设$dp(i, 0/1)$表示前$i$秒进的/没进的人数期望值。因为这样设会无法处理人数限制的情况

知识点:期望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
30
31
32
33
34
35
36
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 2000 + 5;
int n, t;
db p, dp[MAXN][MAXN];
void clean() {
}
int solve() {
clean();
dp[0][0] = 1.0;
for (int i = 1; i <= t; i++) {
for (int j = 0; j <= n; j++) {
if (j != n) dp[i][j] = dp[i - 1][j - 1] * p + dp[i - 1][j] * (1.0 - p);
else dp[i][j] = dp[i - 1][j - 1] * p + dp[i - 1][j];
}
}
db ans = 0;
for (int j = 1; j <= n; j++) ans += dp[t][j] * j;
printf("%.8f\n", ans);
return 0;
}
int main() {
scanf("%d%lf%d", &n, &p, &t), solve();
return 0;
}
------ 本文结束 ------