Poj 1644 To Bet or Not To Bet (概率 DP)

傷城~ 2021-11-01 14:46 203阅读 0赞

题意：棋盘是一个线性表，初始位置0，结束位置m+1，每一轮抛硬币决定向右一步还是两步，概率各为0.5。棋盘每格上都会有一个说明+n，-n，L，或者 0，分别意味着向右走n格，向左走n格，失去一轮机会，无任何说明。给出棋盘的大小，以及棋盘上每一格的说明，求在t轮或者少于t轮便走到终点处的概率。

思路：DP，递推。注意读入方式，以及数组的初始化。

#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;   
    }