转自：https://www.cnblogs.com/kuangbin/archive/2012/10/02/2710606.html

题目大意：

有三个骰子，分别有k1,k2,k3个面。每次掷骰子，如果三个面分别为a,b,c则分数置0，否则加上三个骰子的分数之和。当分数大于n时结束。求游戏的期望步数。初始分数为0。

基本思路：

设dp[i]表示达到i分时到达目标状态的期望，pk为投掷k分的概率，p0为回到0的概率

则dp[i]=∑(pk*dp[i+k])+dp[0]*p0+1;

都和dp[0]有关系，而且dp[0]就是我们所求，为常数

设dp[i]=A[i]*dp[0]+B[i];

代入上述方程右边得到：

dp[i]=∑(pk*A[i+k]*dp[0]+pk*B[i+k])+dp[0]*p0+1

=(∑(pk*A[i+k])+p0)dp[0]+∑(pk*B[i+k])+1；

明显A[i]=(∑(pk*A[i+k])+p0)

B[i]=∑(pk*B[i+k])+1

先递推求得A[0]和B[0].

那么 dp[0]=B[0]/(1-A[0]);

代码如下：

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;double A[600],B[600];double p[100];int main(){    int T;    int k1,k2,k3,a,b,c;    int n;    scanf("%d",&T);    while(T--)    {        scanf("%d%d%d%d%d%d%d",&n,&k1,&k2,&k3,&a,&b,&c);        double p0=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]+=p0;        memset(A,0,sizeof(A));        memset(B,0,sizeof(B));        for(int i=n;i>=0;i--)        {            A[i]=p0;B[i]=1;            for(int j=1;j<=k1+k2+k3;j++)            {                A[i]+=A[i+j]*p[j];                B[i]+=B[i+j]*p[j];            }        }        printf("%.16lf\n",B[0]/(1-A[0]));    }    return 0;}