发布于  更新于 

UVA1541 To Bet or Not To Bet

概率DP 题解 OI

题意

给定一个线性棋盘,每回合抛一次硬币,正面向前走一个,反面向前走两个。走到的格子上面可能有三种操作或者没有操作:

  1. 向前走
  2. 向后走
  3. 跳过下一回合(回合数++

抛完硬币后就执行一次目标格的操作,只执行一次。

问在回合内走到终点或者终点之后的概率(输出格式见原题)。

分析

记忆化搜索,表示第步走到第格的概率。分类讨论抛硬币正面和反面的情况。

走一个的情况:

走两个的情况:

答案就是以上两个值的平均数。

代码

输入格式很恶心。

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

const int MAXN = 100;
const char DOUBLE_MIN = 0xc2;
const double EPS = 1e-8;

bool bad[MAXN];
int offset[MAXN];
double dp[MAXN][MAXN];

int n, t;

double dfs(int i, int j) {
if (dp[i][j] >= 0) return dp[i][j];
if (j == n + 1) return 1; // 走到了
if (i >= t) return 0; // 机会用完了没走到
dp[i][j] = 0;
if (bad[j + 1]) {
dp[i][j] += dfs(i + 2, j + 1) / 2;
} else {
dp[i][j] += dfs(i + 1, j + 1 + offset[j + 1]) / 2;
}
int to = min(n + 1, j + 2); //特判跑出去的情况
if (bad[to]) {
dp[i][j] += dfs(i + 2, to) / 2;
} else {
dp[i][j] += dfs(i + 1, to + offset[to]) / 2;
}
return dp[i][j];
}

int dcmp(double x, double y) {
double c = x - y;
if (c > EPS) return 1;
if (c < -EPS) return -1;
return 0;
}

int main() {
int tcnt;
cin >> tcnt;
for (int T = 1; T <= tcnt; T++) {
cin >> n >> t;
memset(bad, false, sizeof bad);
memset(offset, 0, sizeof offset);
memset(dp, 0xc2, sizeof dp);
for (int i = 1; i <= n; i++) {
char opr[10];
scanf("%s", opr);
if (opr[0] == 'L') {
bad[i] = true;
} else {
offset[i] = floor(atof(opr));
}
}
double ans = dfs(0, 0);
switch(dcmp(ans, 0.5)) {
case 1:
printf("Bet for. %.4lf\n", ans);
break;
case 0:
printf("Push. %.4lf\n", ans);
break;
case -1:
printf("Bet against. %.4lf\n", ans);
break;
}
}
}