本文主要是介绍UVA 1541 - To Bet or Not To Bet(概率递推)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
UVA 1541 - To Bet or Not To Bet
题目链接
题意：这题题意真是神了- -，看半天，大概是玩一个游戏，开始在位置0，终点在位置m + 1,每次扔一个硬币，正面走一步，反面走两步，走到的步上有4种情况：
1、向前走n步
2、向后走n步
3、停止一回合
4、无影响
问能在t次机会内，走到终点m + 1（如果跃过也算走到了)的概率，大于0.5，等于0.5，小于0.5对应不同输出
思路：题意懂了就好办了，其实就是递推就可以了dp[i][j]表示第i次机会，落在j步的概率，然后不断一步步去递推即可
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;const int INF = 0x3f3f3f3f;
const int N = 55;int T, m, t, to[N];
double dp[N][N];int tra() {char str[10];scanf("%s", str);if (str[0] == '0') return 0;if (str[0] == 'L') return INF;else {int num = 0, flag = (str[0] == '+' ? 1 : -1);for (int i = 1; str[i]; i++)num = num * 10 + str[i] - '0';return num * flag;}
}int main() {scanf("%d", &T);while (T--) {scanf("%d%d", &m, &t);for (int i = 1; i <= m; i++)to[i] = tra();to[m + 1] = 0;memset(dp, 0, sizeof(dp));dp[0][0] = 1;for (int i = 0; i <= t; i++) {for (int j = 0; j <= m; j++) {if (to[min(m + 1, j + 1)] == INF)dp[i + 2][min(m + 1, j + 1)] += dp[i][j] * 0.5;elsedp[i + 1][min(max(0, j + 1 + to[min(m + 1, j + 1)]), m + 1)] += dp[i][j] * 0.5;if (to[min(m + 1, j + 2)] == INF)dp[i + 2][min(m + 1, j + 2)] += dp[i][j] * 0.5;elsedp[i + 1][min(max(0, j + 2 + to[min(m + 1, j + 2)]), m + 1)] += dp[i][j] * 0.5; }}double ans = 0;for (int i = 0; i <= t; i++) ans += dp[i][m + 1];if (ans > 0.5) printf("Bet for. ");else if (ans < 0.5) printf("Bet against. ");else printf("Push. ");printf("%.4lf\n", ans);}return 0;
}这篇关于UVA 1541 - To Bet or Not To Bet(概率递推)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
