本文主要是介绍uva 1541 - To Bet or Not To Bet(记忆化+概率)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：uva 1541 - To Bet or Not To Bet
题目大意：在一个棋盘上进行游戏，给定棋盘长度m，不算起始和终止，以及走的步数t。从起点开始，每轮可以丢一枚硬币，正面移动2步，方面移动1步；中间的格子有写操作，包括移动一定步数，停止一次操作。问说在t步内到达终点的概率。
解题思路：dp[i][j]表示走到第i格用掉j步的概率，然后记忆化搜索，因为保证状态重复，并且可以确定递归终止条件。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>using namespace std;
const int maxn = 100;bool lose[maxn], vis[maxn][maxn];
double p[maxn][maxn];
int N, T, inst[maxn];void init () {char str[maxn];memset(inst, 0, sizeof(inst));memset(vis, false, sizeof(vis));memset(lose, false, sizeof(lose));scanf("%d%d", &N, &T);for (int i = 1; i <= N; i++) {scanf("%s", str);if (str[0] == 'L')lose[i] = true;elsesscanf(str, "%d", &inst[i]);}
}double dfs (int d, int k) {if (vis[d][k])return p[d][k];vis[d][k] = true;if (d == N + 1)return p[d][k] = 1;if (k <= 0)return p[d][k] = 0;double& ret = p[d][k];ret = 0;int next = d + 1;if (lose[next])ret += 0.5 * dfs(next, k-2);elseret += 0.5 * dfs(next + inst[next], k - 1);next = min(d + 2, N + 1);if (lose[next])ret += 0.5 * dfs(next, k-2);elseret += 0.5 * dfs(next + inst[next], k - 1);return ret;
}int main () {int cas;scanf("%d", &cas);while (cas--) {init();double ans = dfs(0, T);if (fabs(ans - 0.5) < 1e-9)printf("Push. 0.5000\n");else if (ans > 0.5)printf("Bet for. %.4lf\n", ans);elseprintf("Bet against. %.4lf\n", ans);}return 0;
}这篇关于uva 1541 - To Bet or Not To Bet(记忆化+概率)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
