题目意思是你现在有三个骰子,die1,die2,die3,如果抛出die1=a,die2=b,die3=c,那么你你的积分清零,否则你的积分加上这个三个骰子之和。求你的积分大于n的期望?


这个题比较有意思,就算你想到了递推式也很难想到转化,哈哈。

首先我们假定当前积分是i,那么有递推式:

E[i] = ∑(E[i+k]*p[k]) + E[0]*p[0] + 1                                  

这个递推式的意思是,当前积分是i,抛出一次骰子,会抛出k点,得到这个积分,并且k点的概率为p[k],因为有清零的情况,所以要单独考虑。

递推式出来了,然后我们要求的应该是E[0],但是从递推式可以看出来每个积分递推式的计算都要到了E[0],因为有环,所以怎么办呢?

我们定义一个与E[0]有关的式子:

E[i] = A[i]*E[0]+B[0]                                                            

我们把代入 得到:

E[i] =  (∑(A[i+k]*p[k]) + p[0])*E[0] +  ∑(B[i+k]*p[k]) + 1

然后得出:

A[i] = ∑(A[i+k]*p[k]) + p[0]

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

变换并且代入0可以得到:

E[0] = B[0]/(1-A[0])

然后就求出来啦(提示一下,对于区间,骰子是最低有1,所以k应该从3开始计算)。

代码:

StatusAccepted
Memory296kB
Length1034
LangC++ (g++ 4.7.2)
#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
const int maxn=600;
const int maxp=40;
int t, n, k1, k2, k3, a, b, c;
double pk[maxp], all, sum, A[maxn], B[maxn];
int main()
{
    scanf("%d", &t);
    while(t--){
        scanf("%d%d%d%d%d%d%d", &n, &k1, &k2, &k3, &a, &b, &c);
        memset(A, 0, sizeof(A));
        memset(B, 0, sizeof(B));
        memset(pk, 0, sizeof(pk));
        all=k1*k2*k3;
        sum=k1+k2+k3;
        pk[0]=1.0/all;
        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)continue;
                    pk[i+j+k]++;
                }
            }
        }
        for(int i=3;i<=sum;i++)pk[i]/=all;
        for(int i=n;i>=0;i--){
            for(int j=3;j<=sum;j++){
                A[i]+=(pk[j]*A[i+j]);
                B[i]+=(pk[j]*B[i+j]);
            }
            A[i]+=pk[0];
            B[i]++;
        }
        printf("%.15lf\n", B[0]/(1.0-A[0]));
    }
    return 0;
}