ZOJ-3329 One Person Game （機率DP）

One Person Game http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3754 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 K1 faces. Die2 has K2 faces. Die3 has K3 faces. All the dice are fair dice, so the probability of rolling each value, 1 to K1, K2, K3 is exactly 1 / K1, 1 / K2 and 1 / K3. You have a counter, and the game is played as follow:

1. Set the counter to 0 at first.
2. 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.
3. 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, K1, K2, K3, a, b, c (0 <= n <= 500, 1 < K1, K2, K3 <= 6, 1 <= a <= K1, 1 <= b <= K2, 1 <= c <= K3).

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      

題目大意：有三個分别有k1,k2,k3面的骰子，計數器初始為0，每次加上三個骰子點數和，若k1==a&&k2==b&&k3==c，則計數器清零，求最終點數超過n的擲骰子次數的期望？

設dp[i]表示點數i離目标狀态還需擲骰子次數的期望

狀态轉移方程很好想：dp[i]=∑(p[k]*dp[i+k])+1/(k1*k2*k3)*dp[0]+1;                                                                ①

但是由于存在dp[0]，是以沒法直接使用

剛開始我用dp[i]-dp[i+1]求出一個方程，然而右邊常數項沒了，就沒法進行轉移。。。

看了題解後才發現：由于dp[i]與dp[0]都有線性關系，是以可以設系數a[i],b[i]，令dp[i]=a[i]*dp[0]+b[i];      ②

将②式帶入①式右邊可得：dp[i]=∑(p[k]*(a[i+k]*dp[0]+b[i+k]))+1/(k1*k2*k3)*dp[0]+1;

整理可得：dp[i]=∑(p[k]*a[i+k]+1/(k1*k2*k3))*dp[0]+∑(p[k]*b[i+k])+1;                                                             ③

對比②③右邊可得：

a[i]=∑(p[k]*a[i+k]+1/(k1*k2*k3));

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

【上述各式中：3<=k&&k<=k1*k2*k3】

而dp[0]=a[0]*dp[0]+b[0] 可以推出：dp[0]=b[0]/(1-a[0]);

是以可以先推出a[0]和b[0]，再求出dp[0];

感覺機率dp就是數列求能夠直接遞推的遞推公式

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int n,k1,k2,k3,x,y,z;
double a[625],b[625],p[225],sum;

int main() {
    int T;
    scanf("%d",&T);
    while(T-->0) {
        scanf("%d%d%d%d%d%d%d",&n,&k1,&k2,&k3,&x,&y,&z);
        memset(p,0,sizeof(p));
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        for(int i=1;i<=k1;++i) {
            for(int j=1;j<=k2;++j) {
                for(int k=1;k<=k3;++k) {
                    p[i+j+k]+=1;
                }
            }
        }
        sum=k1*k2*k3;
        p[0]=1;
        p[x+y+z]-=1;
        for(int i=sum;i>=0;--i) {
            p[i]/=sum;
        }
        for(int i=n;i>=0;--i) {
            a[i]=p[0];
            b[i]=1;
            for(int k=3;k<=sum;++k) {
                a[i]+=p[k]*a[i+k];
                b[i]+=p[k]*b[i+k];
            }
        }
        printf("%.15lf\n",b[0]/(1-a[0]));
    }
    return 0;
}