HDU 4089 && UVa 1498 Activation 带环的概率DP

　　　　要在HDU上交的话，要用滚动数组优化一下空间。

　　　　这道题想了很久，也算是想明白了，就好好写一下吧。

　　　　P₁：激活游戏失败，再次尝试。

　　　　P₂：连接失服务器败，从队首排到队尾。

　　　　P₃：激活游戏成功，队首的人出队。

　　　　P₄：服务器down掉，所有人都不能激活了。

　　　　设d(i, j)表示i个人排队，主人公排在第j位，发生所求事件的概率。

　　　　d(i, 1) = P₁ d(i, 1) + P₂ d(i, i) + P₄ //分别对应激活失败，重新尝试；连接失败排到队尾；服务器down掉

　　　　特殊地可以直接计算出 d(1, 1) = (P₁ + P₂) d(1, 1) + P₄

　　　　得到： $d(1,1)=\frac{P_{4}}{1-P_{1}-P_{2}}$

　　　　① j ≤ k， $d(i,j)=P_{1}\, d(i, j) + P_{2}\, d(i, j-1) + P_{3}\, d(i-1,j-1) +P_{4}$

　　　　② j > k， $d(i,j)=P_{1}\, d(i, j) + P_{2}\, d(i, j-1) + P_{3}\, d(i-1,j-1)$

　　　　令 $P_{21}=\frac{P_{2}}{1-P_{1}},P_{31}=\frac{P_{3}}{1-P_{1}},P_{41}=\frac{P_{4}}{1-P_{1}}$

　　　　整理上面两个式子得到：

　　　　 $d(i,1)=P_{21}d(i,i)+P_{41}$

　　　　 $d(i, j)=\left\{\begin{matrix} P_{21}d(i,j-1)+P_{31}d(i-1,j-1)+P_{41},j\leq k\\ P_{21}d(i,j-1)+P_{31}d(i-1,j-1),j> k \end{matrix}\right.$

　　　　因为是在递推，所以在计算d(i, j)的时候，d(i-1, j-1)的值已经计算出来了。

　　　　从d(i, i)开始一直迭代到d(i, 1) (共迭代i-1次)，可以计算出一个d(i, i)和d(i, 1)的关系式，不妨设计算出来的为：d(i, i) = a × d(i, 1) + b

　　　　然后再把d(i, i)与d(i, 1)的关系代入： $d(i,i)=\frac{bP_{21}}{1-aP_{21}}$

　　　　事实上这里系数a可以直接计算出为： ${P_{21}}^{i-1}$

　　　　这样就能计算出d(i, 1)和d(i, i)，其他的就可以按照最开始的式子递推了。

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 using namespace std;

 const int maxn =  + ;

 int n, m, k;

 double p1, p2, p3, p4;

 double d[][maxn];

 const double eps = 1e-;

 int dcmp(double x)

 {

     if(fabs(x) < eps) return ;

     return x <  ? - : ;

 }

 int main()

 {

     while(scanf("%d%d%d", &n, &m, &k) ==  && n)

     {

         scanf("%lf%lf%lf%lf", &p1, &p2, &p3, &p4);

         if(dcmp(p3 - ) ==  || dcmp(p4) == ) { puts("0.00000"); continue; }

         memset(d, , sizeof(d));

         d[][] = p4 / (1.0 - p1 - p2);

         double p21 = p2 / (1.0 - p1);

         double p31 = p3 / (1.0 - p1);

         double p41 = p4 / (1.0 - p1);

         int cur = ;

         for(int i = ; i <= n; i++)

         {

             cur =  - cur;

             double a = 1.0, b = ;

             for(int j = ; j <= i; j++)

             {

                 a *= p21;

                 b = b * p21 + d[-cur][j-] * p31;

                 if(j <= k) b += p41;

             }

             d[cur][i] = (a * p41 + b) / (1.0 - a * p21);

             d[cur][] = p21 * d[cur][i] + p41;

             for(int j = ; j < i; j++)

             {

                 d[cur][j] = p21 * d[cur][j-] + p31 * d[-cur][j-];

                 if(j <= k) d[cur][j] += p41;

             }

         }

         printf("%.5f\n", d[cur][m]);

     }

     return ;

 }

代码君

巴特西

HDU 4089 && UVa 1498 Activation 带环的概率DP

最新文章

热门文章