ZOJ 3329 One Person Game 概率DP 好题

One Person Game

Time Limit: 1 Second Memory Limit: 32768 KB Special Judge

There is a very simple and interesting one-person game. You have 3 dice, namely Die1, Die2 and Die3. Die1 has K₁ faces. Die2 has K₂ faces. Die3 has K₃faces. All the dice are fair dice, so the probability of rolling each value, 1 to K₁, K₂, K₃ is exactly 1 / K₁, 1 / K₂ and 1 / K₃. You have a counter, and the game is played as follow:

Set the counter to 0 at first.
Roll the 3 dice simultaneously. If the up-facing number of Die1 is a, the up-facing number of Die2 is b and the up-facing number of Die3 is c, set the counter to 0. Otherwise, add the counter by the total value of the 3 up-facing numbers.
If the counter's number is still not greater than n, go to step 2. Otherwise the game is ended.

Calculate the expectation of the number of times that you cast dice before the end of the game.

Input

There are multiple test cases. The first line of input is an integer T (0 < T <= 300) indicating the number of test cases. Then T test cases follow. Each test case is a line contains 7 non-negative integers n, K₁, K₂, K₃, a, b, c (0 <= n <= 500, 1 < K₁, K₂, K₃ <= 6, 1 <= a <= K₁, 1 <= b <= K₂, 1 <= c <= K₃).

Output

For each test case, output the answer in a single line. A relative error of 1e-8 will be accepted.

Sample Input

2
0 2 2 2 1 1 1
0 6 6 6 1 1 1

Sample Output

1.142857142857143
1.004651162790698

Author: CAO, Peng
Source: The 7th Zhejiang Provincial Collegiate Programming Contest

题意：有三个均匀的骰子，分别有k1,k2,k3个面，你的初始分数是0，
　当掷三个骰子的点数分别为a,b,c的时候，分数清零，否则分数加上三个骰子的点数和，
当分数>n的时候结束。求需要掷骰子的次数的期望。

这道题真的很好，写下自己的思路在代码前面。

  1 /*
  2 
  3 令dp[i]表示当前点数是i，到达点数>n的状态时期望的步数
  4 明显，i>n时，dp[i]=0.0
  5 设k=(double)k1*k2*K3,方便计算
  6 设点数i加上投出来的点数之后为j
  7 则：dp[i]=1.0/k*(dp[0]+1)+1/k*[∑dp[j]+1]  //这里求和的有k-1个，k种可能-1种情况
  8          =1/k*dp[0]+1/k+1/k*∑dp[j]+(k-1)/k
  9          =1/k*dp[0]+1/k*∑dp[j]+1
 10 
 11 可以看到，这里dp[i]与dp[j]和dp[0]有关，dp[j]又和dp[0]有关
 12 而我们要求的就是dp[0],则dp[0]是一个定值
 13 这样是没有办法直接通过递推得到dp[0]了
 14 
 15 则设dp[i]=A[i]*dp[0]+B[i]
 16 有：dp[j]+A[j]*dp[0]+B[j]
 17 ∑dp[j]=dp[0]*∑A[j]+∑B[j]
 18 带入dp[i]的式子，有：
 19 dp[i]=1/k*dp[0]+1/k*dp[0]*∑A[j]+1/k∑B[j]+1
 20      =1/k(1+∑A[j])dp[0]+1/k∑B[j]+1
 21 
 22 这样就可以消去开始时候的式子的dp[j]了
 23 还得到：
 24 当i>n,
 25 A[i]=0
 26 B[i]=0
 27 当i<=n,
 28 A[i]=1/k(1+∑A[j])
 29 B[i]=1/k∑B[j]+1
 30 这样数组A，B就可以通过递推得到了
 31 其中，j是指点数i通过加上骰子的点数后可以到达的点数，注意投出a,b,c时不算
 32 则有：dp[0]=A[0]*dp[0]+B[0]
 33       dp[0]=B[0]/(1.0-A[0])
 34       
 35 这样，只要递推求出了A[0],B[0],带入即可得dp[0]
 36 
 37 注意：
 38 点数清0的情况是当k1,k2,k3投出的点数分别为a,b,c的时候
 39 而不是当投出的点数之和是a+b+c的时候
 40 
 41 因为这个wa了2次
 42 
 43 */
 44 
 45 
 46 #include<cstdio>
 47 
 48 const int maxn=600;
 49 
 50 double A[maxn];
 51 double B[maxn];
 52 double k;
 53 int k1,k2,k3;
 54 int a,b,c;
 55 
 56 double solve(int n)
 57 {
 58     for(int i=n+1;i<n+30;i++)
 59     {
 60         A[i]=0.0;
 61         B[i]=0.0;
 62     }
 63 
 64     for(int i=n;i>=0;i--)
 65     {
 66         double cnta=0.0;
 67         double cntb=0.0;
 68         for(int j1=1;j1<=k1;j1++)
 69         {
 70             for(int j2=1;j2<=k2;j2++)
 71             {
 72                 for(int j3=1;j3<=k3;j3++)
 73                 {
 74                     //这里开始写成j1+j2+j3==a+b+c，wa了2次
 75                     if(j1==a&&j2==b&&j3==c)
 76                         continue;
 77                     cnta+=A[i+j1+j2+j3];
 78                     cntb+=B[i+j1+j2+j3];
 79                 }
 80             }
 81         }
 82         A[i]=(1.0+cnta)/k;
 83         B[i]=cntb/k+1.0;
 84     }
 85 
 86     return B[0]/(1.0-A[0]);
 87 }
 88 
 89 int main()
 90 {
 91     int test;
 92     scanf("%d",&test);
 93     while(test--)
 94     {
 95         int n;
 96         scanf("%d",&n);
 97         scanf("%d%d%d",&k1,&k2,&k3);
 98         scanf("%d%d%d",&a,&b,&c);
 99 
100         k=(double)k1*k2*k3;
101 
102         printf("%.15f
",solve(n));
103     }
104     return 0;
105 }

View Code