UVA1541 To Bet or Not To Bet

04 June 2019 | duanyll | Tags: OI 题解 概率DP

题意

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

1. 向前走$n$格
2. 向后走$n$格
3. 跳过下一回合（回合数++）

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

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

分析

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

走一个的情况：

\[dfs(i,j)=\left\{ \begin{array}{ll} dfs(i+2,j+1) & \textrm{j+1格是停一回合}\\ dfs(i+1,j+1+offset[j+1]) & \textrm{j+1格不是停一回合} \end{array} \right.\]

走两个的情况：

\[dfs(i,j)=\left\{ \begin{array}{ll} dfs(i+2,j+2) & \textrm{j+2格是停一回合}\\ dfs(i+1,j+2+offset[j+2]) & \textrm{j+2格不是停一回合} \end{array} \right.\]

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

代码

输入格式很恶心。

#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;
		}
	}
}