[機率DP] Topcoder SRM687div2 1000 Queueing

題意：

兩列隊伍，左邊有 len1 個人，右邊有 len2 個人，問事件左邊沒人但右邊有人的機率。

兩邊收銀員各有一個經驗值參數 p ，F(p,k)=(1/p)∗(1−1/p)k−1表示經驗值為 p 的收銀員恰好花費k秒完成一次收銀的機率。

題解：

首先發現 F(p,k) 十分眼熟，滿足幾何分布，是以每秒成功收銀的機率是 1/p ，設左邊成功收銀機率 a=1/p1 ，右邊為 b=1/p2 。

設左邊沒人但右邊有人為事件 A ，則答案是求P(A)

然後就是DP， DP[i][j] 表示左邊有 i 人右邊有j人時達成事件 A 的機率。

然後轉移有四個方向：

1. 左邊成功但右邊失敗，機率是a∗(1−b)
   • 左邊成功且右邊成功，機率是 a∗b
   • 左邊失敗但右邊成功，機率是 (1−a)∗b
   • 左邊失敗且右邊失敗，機率是 (1−a)(1−b)

   • 整理出轉移方程。

     DP[i][j]=DP[i−1][j]∗a∗(1−b)+DP[i−1][j−1]∗a∗b+DP[i][j−1]∗(1−a)∗b+DP[i][j]∗(1−a)∗(1−b)

     解出 DP[i][j]=(DP[i−1][j]∗a∗(1−b)+DP[i−1][j−1]∗a∗b+DP[i][j−1]∗(1−a)∗b)/(1−(1−a)∗(1−b)) 。

     初始條件為 DP[0][0]=0，DP[0][i]=1(i>=1) 。

     // BEGIN CUT HERE
     
     // END CUT HERE
     #line 5 "Queueing.cpp"
     #include<vector>
     #include<algorithm>
     #include<string.h>
     using namespace std;
     double dp[][];
     class Queueing {
         private:
             void init(){
                 memset(dp, , sizeof(dp));
             }
         public:
             double probFirst(int len1, int len2, int p1, int p2) {
                 init();
                 for(int i = ; i <= len2; ++i) dp[][i] = ;
                 double a = /p1, b = /p2;
                 for(int i = ; i <= len1; ++i){
                     for(int j = ; j <= len2; ++j){
                         dp[i][j] = dp[i-][j]*a*(-b)+dp[i][j-]*(-a)*b+dp[i-][j-]*a*b;
                         dp[i][j] /= (-(-a)*(-b));
                     }
                 }
                 return dp[len1][len2];
             }
     };