题目链接：uva 1541 - To Bet or Not To Bet

题目大意：在一个棋盘上进行游戏，给定棋盘长度m，不算起始和终止，以及走的步数t。从起点开始，每轮可以丢一枚硬币，正面移动2步，方面移动1步；中间的格子有写操作，包括移动一定步数，停止一次操作。问说在t步内到达终点的概率。

解题思路：dp[i][j]表示走到第i格用掉j步的概率，然后记忆化搜索，因为保证状态重复，并且可以确定递归终止条件。

#include 
   
     #include 
    
      #include 
     
       #include 
      
        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; else sscanf(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); else ret += 0.5 * dfs(next + inst[next], k - 1); next = min(d + 2, N + 1); if (lose[next]) ret += 0.5 * dfs(next, k-2); else ret += 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); else printf("Bet against. %.4lf\n", ans); } return 0; }