题目分析

问题描述

给定一个棋盘布局和目标回合数 $T$，计算游戏在 $T$ 回合或更少回合内结束的概率。棋子初始位于“起始”方格（位置 $0$），每回合抛硬币决定移动 $1$ 格（正面）或 $2$ 格（反面），随后执行所落方格的指令（右移、左移、跳过回合或无操作）。需判断结束概率是否超过 $50\%$，并按要求输出结果。

解题思路

核心思想

使用 概率动态规划（概率DP） 维护每个回合在不同位置的概率，通过状态转移模拟抛硬币和指令执行过程，最终累计 $T$ 回合内到达终点的概率。

状态定义

• $dp[i][j]$：表示在第 $i$ 回合位于位置 $j$ 的概率。
  • 位置范围：起始位置为 $0$，终点为 $m+1$，中间 $m$ 个内部方格为 $1$ 到 $m$。

状态转移

1. 初始状态：$dp[0][0] = 1.0$（第 $0$ 回合初始位于起始位置）。
2. 抛硬币处理：
   • 正面（移动 $1$ 格）：从位置 $j$ 移动到 $j+1$，概率为 $0.5$。
   • 反面（移动 $2$ 格）：从位置 $j$ 移动到 $j+2$，概率为 $0.5$（若 $j+2$ 超过终点则直接到达终点）。
3. 指令处理：
   • $L$（跳过回合）：执行后当前回合结束，下一回合不进行操作，故回合数增加 $2$（$i+2$）。
   • 数值指令（$+n$ 或 $-n$）：直接按指令移动，回合数增加 $1$（$i+1$）。
   • 无指令（$0$）：不改变位置，回合数增加 $1$。

边界条件

• 终点位置为 $m+1$，到达后游戏结束，后续回合不再处理。
• 输入中的 $L$ 指令转换为 $INF$，便于在代码中统一判断。

代码解析

输入处理

• 读取棋盘大小 $m$ 和目标回合数 $T$，以及每个内部方格的指令。
• 初始化 $dp[0][0] = 1.0$，其余状态概率为 $0$。

动态规划转移

for (i=0; i<t; i++)
    for (j=0; j<m+1; j++)
    {
        // 处理正面（移动 1 格）
        if (data[j+1] == INF)    // 指令为 L，跳过一回合，回合数 +2
            dp[i+2][j+1] += dp[i][j] * 0.5;
        else                     // 执行指令，回合数 +1
            dp[i+1][j + data[j+1] + 1] += dp[i][j] * 0.5;  // 注意位置偏移
        
        // 处理反面（移动 2 格）
        if (data[j+2] == INF)
            dp[i+2][j+2] += dp[i][j] * 0.5;
        else
            dp[i+1][j + data[j+2] + 2] += dp[i][j] * 0.5;
    }

• 对每个回合 $i$ 和位置 $j$，分别处理正面和反面的移动，根据指令更新目标位置和回合数。
• 指令为数值时，直接按指令调整位置（如 $+n$ 对应 $data[j] = n$，$-n$ 对应 $data[j] = -n$）。

结果计算

累计所有 $i \leq T$ 回合到达终点（位置 $m+1$）的概率，根据概率判断输出结果，注意精度处理（使用 $fabs$ 比较是否等于 $0.5$）。

复杂度分析

• 时间复杂度：$O(T \times m)$，其中 $T \leq 40$，$m \leq 50$，完全满足题目约束。
• 空间复杂度：$O(T \times m)$，使用二维数组存储动态规划状态，空间占用小。

关键点

1. 指令处理：将 $L$ 转换为特殊值（$INF$），简化条件判断逻辑。
2. 回合数调整：遇到 $L$ 指令时，回合数增加 $2$（跳过当前回合），其他指令回合数增加 $1$。
3. 精度控制：使用浮点数运算时，通过 $fabs(ans - 0.5) < 1e-9$ 判断是否为精确 $0.5$，避免浮点误差影响结果。

完整代码如下

#include <cstdio>
#include <cstring>
#include <cmath>
 
const int N=60;
const int INF=0x3fffffff;
 
int m,t;
int data[N];
double dp[N][N];  //dp[i][j]能在i步走到j位置的概率
 
void Input ()
{
	char str[10];
	scanf("%d%d",&m,&t);
	memset(dp,0,sizeof(dp));
	data[0]=0,data[m+1]=0;
	data[m+2]=-1;     //超过终点算终点
	for (int i=1;i<=m;i++)
	{
		scanf("%s",str);    
		if (str[0]=='L')
			data[i]=INF;
		else
			sscanf(str,"%d",&data[i]);
	}
	dp[0][0]=1.0;
}
 
int main ()
{
	int T,i,j;
	scanf("%d",&T);
	while (T--)
	{
		Input();
		for (i=0;i<t;i++)
			for (j=0;j<m+1;j++)
			{
				if (data[j+1]==INF)    //若下一格为停留一回合
					dp[i+2][j+1]+=dp[i][j]*0.5;
				else
					dp[i+1][j+data[j+1]+1]+=dp[i][j]*0.5;
				if (data[j+2]==INF)
					dp[i+2][j+2]+=dp[i][j]*0.5;
				else
					dp[i+1][j+data[j+2]+2]+=dp[i][j]*0.5;
			}
		double ans=0;
		for (i=0;i<=t;i++)
			ans+=dp[i][m+1];     //统计所有能在t回合以内走到m+1点的概率
		if (fabs(ans-0.5)<1e-9)  //注意精度
			printf("Push. 0.5000\n");
		else if (ans<0.5)
			printf("Bet against. %.4lf\n",ans);
		else
			printf("Bet for. %.4lf\n",ans);
	}
	return 0;   
}