【ZOJ3329】One Person Game

题意

你有三枚色子，第i个色子有ki面，你有一个计数器。

1.开始的时候将计数器调至0

2.扔三个色子，如果色子1是a，色子2是b，色子3是c，则将计数器归零。否则计数器加上三个色子的和。

3.如果计数器的数字大于等于n游戏结束，否则重复步骤

计算扔色子次数的期望

分析

通过带入系数解决概率DP问题。

f[i]为当前计数器的数字是i，到游戏结束的期望次数是多少。

f[i]=sum(f[i+k]*p)+1+f[0]*p。

因为f[0]就是我们所求的东西，所以我们令f[i]=A[i]*f[0]+B[i]

带入整理得f[i]=(sum(A[i+k]*p)+p)*f[0]+sum(p*B[i+k])+1

观察得到 A[i]=sum(p*A[i+k])+p

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

ans=f[0]=B[0]/(1-A[0])

 #include <cstdio>
 #include <cstring>
 #include <algorithm>
 #include <iostream> using namespace std;
 const int maxn=;
 double A[maxn],B[maxn];
 int T,n,K1,K2,K3,a,b,c; int main(){
     scanf("%d",&T);
     for(int t=;t<=T;t++){
         scanf("%d%d%d%d%d%d%d",&n,&K1,&K2,&K3,&a,&b,&c);
         memset(A,,sizeof(A));
         memset(B,,sizeof(B));
         for(int i=;i<=n;i++){
             for(int j=;j<=K1;j++){
                 for(int k=;k<=K2;k++){
                     for(int l=;l<=K3;l++){
                         if(j!=a||k!=b||l!=c){
                             int sum=j+k+l;
                             if(i-sum>=){
                                 A[i]+=A[i-sum]*(double)/(K1*K2*K3);
                                 B[i]+=B[i-sum]*(double)/(K1*K2*K3);
                             }
                         }
                     }
                 }
             }
             A[i]+=(double)/(K1*K2*K3);
             B[i]+=;
         }
         double ans=B[n]/(-A[n]);
         printf("%.15f\n",ans);
     }
 return ;
 }