POJ 3756 Chess Game(概率问题)
转载请注明出处，谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526 by---cxlove
题目：给出一个棋类游戏，掷筛子决定前进几步。有些格子可能有一些指示，如前进几步，后退几步以及暂停一次。
问到达终点的期望步数为多少。
http://poj.org/problem?id=3756
又是一个有环的求期望问题，之前写一个记忆化搜索，果断不对。
dp[i][j]表示第i步走到第j个格子时的概率。最终枚举步数就行了。
这里选定一个步数上界，感觉这题和别的题目都不一样。。。这里需要仔细考虑
#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<cmath>#include<string>#include<vector>#include<algorithm>#include<map>#include<set>#define eps 1e-8#define zero(a) fabs(a)<epsusing namespace std;int n,m,u,v;int step[105],stop[105];double dp[1005][105];int main(){while(scanf("%d",&n)!=EOF){memset(step,0,sizeof(step));memset(stop,0,sizeof(stop));scanf("%d",&m);while(m--){scanf("%d%d",&u,&v);step[u]=v;}scanf("%d",&m);while(m--){scanf("%d%d",&u,&v);step[u]=-v;}scanf("%d",&m);while(m--){scanf("%d",&u);stop[u]=1;}memset(dp,0,sizeof(dp));dp[0][0]=1;for(int i=1;i<1000;i++){for(int j=0;j<n;j++){if(zero(dp[i-1][j])) continue;for(int k=1;k<=6;k++){int cur=j+k;if(cur>n) cur=2*n-cur;if(stop[cur]){dp[i+1][cur]+=1.0/6*dp[i-1][j];continue;}cur+=step[cur];if(cur>n) cur=2*n-cur;if(cur<0) cur=-cur;dp[i][cur]+=1.0/6*dp[i-1][j];}}}double ans=0;for(int i=1;i<1000;i++)ans+=i*dp[i][n];if(zero(ans)) puts("Impossible");else printf("%.2f\n",ans);}return 0;}