ZOJ 3329 One Person Game（概率问题）
转载请注明出处，谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526 by---cxlove
题目：有3个筛子，分别有k1,k2,k3个面。每次掷筛子，如果三个面为指定的a,b,c，则分数置0，否则加上三个筛子的和。当总分大于等于n结束。求游戏的期望步数
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3754
E[i]表示分数为i时的期望步数，当i>=n时，E[i]=0，题目要求的即是E[0]。
E[i]=sigma(E[i+k]*Pk)+E[0]*P0+1。其中Pk表示三个筛子和为k的概率，其中不包括指定的那种
其中P0就是指定的那种的概率。
可以发现这还是一个有环的期望问题，然后就是得迭代迭代然后化简了。。
E[0]为所求，而且每一个E[i]中都有E[0]。
令E[i]=a[i]*E[0]+b[i]。得到E[i]=(sigma(a[i+k])+P0)*E[0]+sigma(b[i+k])+1
便得到a[i]=sigma(a[i+k])+P0,b[i]=sigma(b[i+k])+1。
最终E[0]=b[0]/(1-a[0])
#include<iostream>#include<cstdio>#include<cstring>using namespace std;double p[20],pa[1005],pb[1005];int n,k1,k2,k3,a,b,c;int main(){ int t; scanf("%d",&t); while(t--){ scanf("%d%d%d%d%d%d%d",&n,&k1,&k2,&k3,&a,&b,&c); double one=1.0/(k1*k2*k3); memset(p,0,sizeof(p)); for(int i=1;i<=k1;i++) for(int j=1;j<=k2;j++) for(int k=1;k<=k3;k++) if(i!=a||j!=b||k!=c) p[i+j+k]+=one; memset(pa,0,sizeof(pa)); memset(pb,0,sizeof(pb)); for(int i=n;i>=0;i--){ for(int j=3;j<=k1+k2+k3&&(i+j)<=n;j++){ pa[i]+=pa[i+j]*p[j]; pb[i]+=pb[i+j]*p[j]; } pa[i]+=one; pb[i]+=1; } printf("%.15f\n",pb[0]/(1-pa[0])); } return 0;}