ZOJ 3640 Help Me Escape(概率DP)

题目大意

Cain被困在一座有 $N$ 条路径的洞穴,他本身有战斗力为 $f$ 。
每一天,Cain会被随机传送到某条路径:
若他此时的战斗力大于该路径的困难度 $c_i$ ,那么他可以花费 $t_i$ 时间逃出这个洞穴;
否则,无法逃出洞穴,但其战斗力可以增加 $c_i$ ,并等待第二天的传送。
求Cain逃出洞穴的期望时间。

$( N \leq 100, f \leq 10000, c_i \leq 10000, 1 \leq i \leq N )$
$( t_i = \lfloor \frac{1 + \sqrt{5}}{2} \rfloor \times c_i^{2} )$

解题思路

概率DP

设 $dp[i][j]$ 表示Cain在第 $i$ 条路径,战斗力为 $j$ 时的期望时间。
则其转移方程为
$$ dp[i][j] = (\sum_{i=1}^n dp[i][j + c_i] + 1) / n (j \leq c_i) $$
直接记忆化搜索就可以了。

注意其实还有一个优化,根据题意,无论Cain今天在哪条路径上,第二天被传送到任何一条路径的概率是相等的,也即他可能还会出现在今天这条路径上,所以上述转移方程的第一维其实是不需要的,只关注战斗力本身就可以了(详细请看代码)。

另外:由于本题的dp是double型,不能直接memset为某个值(可能会出现误差), 可以考虑多增加一个数组判断是否访问或者直接手动对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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>

using namespace std;

typedef long long ll;

const int MAXN = 1e2 + 10;
const int MAXM = 1e4 + 10;

int n, f;
int c[MAXN], t[MAXN];
bool vis[MAXM];
double dp[MAXM];

double dfs(int cap)
{

if( vis[cap] ) return dp[cap];

double &v = dp[cap];
v = 0;
for( int i = 0; i < n; ++ i )
{
if( cap > c[i] ) v += t[i];
else v += dfs(cap + c[i]) + 1;
}
v /= n;
return v;
}
int main()
{

while( ~scanf("%d %d", &n, &f) )
{
memset(vis, 0, sizeof(vis));
for( int i = 0; i < n; ++ i )
{
scanf("%d", c + i);
t[i] = int((1.0 + sqrt(5.0)) / 2 * c[i] * c[i]);
}
printf("%.3f\n", dfs(f));
}

return 0;
}
如果您觉得这篇博文对您有所帮助,可以考虑请我吃颗糖哦!