LightOJ1395 | UVA12411 A Dangerous Maze (II)
概率dp
题解
oi
题意
你在一个迷宫里，有条路，你每次选择一条，花费时间尝试走这条路，一些路会把你送到出口，另一些路会让你回到起点（已知），你不会走最近次走过的路口，问走出迷宫需要时间的期望，如果不能走出迷宫，输出
分析
首先，在期望的条件下，具体每个门的耗时是不重要的，我们只需知道平均每扇能走出去的门的耗时是，不能走出去的门的耗时是，出口有个，不是出口的有个。定义代表走了次后走出去的期望，代表最终走出来的期望（达到次后再多走都和原来是一样的了），那么
移项得
对于的情况，则令
再考虑不到步就走出去了的情况
最后答案就是
代码
考虑到精度问题，代码中的s1、s2是没有除的。
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
37
38
39
40
41
42
43
44
45
46
47
| #include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 110;
double dp[MAXN];
int main() {
int tcnt;
cin >> tcnt;
for (int T = 1; T <= tcnt; T++) {
int n, k;
cin >> n >> k;
double s1 = 0, s2 = 0;
int a = 0, b = 0;
for (int i = 1; i <= n; i++) {
double x;
cin >> x;
if (x > 0) {
s1 += x;
a++;
} else {
s2 -= x;
b++;
}
}
if (b == n) {
printf("Case %d: %.3lf\n", T, -1.0);
continue;
}
if (k >= b) {
k = b;
dp[k] = s1 / a;
} else {
dp[k] = s1 / a + ((b - k) * s2 / b) / a;
}
for (int i = k - 1; i >= 0; i--) {
dp[i] = (s1 + (b - i) * (s2 / b + dp[i + 1])) / (n - i);
}
printf("Case %d: %.3lf\n", T, dp[0]);
}
}
|
