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;

 				else

 					dp[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;

 				else

 					dp[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;

}