ZOJ Problem Set

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

 设 E[i]表示现在分数为i，到结束游戏所要掷骰子的次数的期望值。

 显然 E[>n] = 0; E[0]即为所求答案;

 E[i] = ∑Pk*E[i+k] + P0*E[0] + 1; (Pk表示点数和为k的概率，P0表示分数清零的概率) 

 由上式发现每个 E[i]都包含 E[0]，而 E[0]又是我们要求的，是个定值。

 设 E[i] = a[i]*E[0] + b[i];

 将其带入上面的式子：  E[i] = ( ∑Pk*a[i+k] + P0 )*E[0] + ∑Pk*b[i+k] + 1;

 显然， 

   a[i] = ∑Pk*a[i+k] + P0; 

   b[i] = ∑Pk*b[i+k] + 1; 

  当 i > n 时： 

  E[i] = a[i]*E[0] + b[i] = 0; 

 所以 a[i>n] = b[i>n] = 0;  
 可依次算出 a[n],b[n]; a[n-1],b[n-1] ... a[0],b[0]; 
 则 E[0] = b[0]/(1 - a[0]); 

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int main()
{
    int t,n,k1,k2,k3,a,b,c;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d %d %d %d %d %d",&n,&k1,&k2,&k3,&a,&b,&c);
        int sum=k1+k2+k3;
        double pp=1.0/(k1*k2*k3);
        double p[10000];
        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]+=pp;
            }
                
        }
        double a[1000]= {0},b[1000]= {0};
        for(int i=n; i>=0; i--)
        {
            for(int k=3; k<=sum; k++)
            {
                a[i]+=a[i+k]*p[k];
                b[i]+=b[i+k]*p[k];
            }
            a[i]+=pp;
            b[i]+=1;
        }
        printf("%.15lf
",b[0]/(1-a[0]));
    }
    return 0;
}