Activation

admin管理员组

文章数量:1122850

Activation

题目：

有 n n n个人排队等着在官网上激活游戏。 T o m a t o Tomato Tomato排在第 m m m个。
对于队列中的第一个人。有以下情况：
1、激活失败，留在队列中等待下一次激活(概率为 p 1 p_1 p1​)
2、失去连接，出队列，然后排在队列的最后(概率为 p 2 p_2 p2​)
3、激活成功，离开队列(概率为 p 3 p_3 p3​)
4、服务器瘫痪，服务器停止激活，所有人都无法激活了(概率 p 4 p_4 p4​)。
求服务器瘫痪时 T o m a t o Tomato Tomato在队列中的位置 < = k ( k ≥ 1 ) <=k(k\ge 1) <=k(k≥1)的概率。

思路：
令 f ( i , j ) f(i,j) f(i,j)表示队列中有 i i i个人， T o m a t o Tomato Tomato在第 j j j个时的状态到最终要求状态的概率，有
f ( i , j ) = { p 1 f ( i , j ) + p 2 f ( i , i ) + p 4 j = 1 p 1 f ( i , j ) + p 2 f ( i , j − 1 ) + p 3 f ( i − 1 , j − 1 ) + p 4 2 ≤ j ≤ k p 1 f ( i , j ) + p 2 f ( i , j − 1 ) + p 3 f ( i − 1 , j − 1 ) j ≥ k + 1 f(i,j)=\begin{cases} p_1f(i,j)+p_2f(i,i)+p_4\quad j=1\\ p_1f(i,j)+p2f(i,j-1)+p_3f(i-1,j-1)+p_4\quad 2\le j\le k\\ p_1f(i,j)+p2f(i,j-1)+p_3f(i-1,j-1)\quad j\ge k+1\\ \end{cases} f(i,j)=⎩⎪⎨⎪⎧​p1​f(i,j)+p2​f(i,i)+p4​j=1p1​f(i,j)+p2f(i,j−1)+p3​f(i−1,j−1)+p4​2≤j≤kp1​f(i,j)+p2f(i,j−1)+p3​f(i−1,j−1)j≥k+1​
分析一下 4 4 4种情况会到哪些状态即可。移项得
f ( i , j ) = { p 2 f ( i , i ) + p 4 1 − p 1 j = 1 p 2 f ( i , j − 1 ) + p 3 f ( i − 1 , j − 1 ) + p 4 1 − p 1 2 ≤ j ≤ k p 2 f ( i , j − 1 ) + p 3 f ( i − 1 , j − 1 ) 1 − p 1 j ≥ k + 1 f(i,j)=\begin{cases} \frac{p_2f(i,i)+p_4}{1-p_1}\quad j=1\\ \frac{p2f(i,j-1)+p_3f(i-1,j-1)+p_4}{1-p_1}\quad 2\le j\le k\\ \frac{p2f(i,j-1)+p_3f(i-1,j-1)}{1-p_1}\quad j\ge k+1\\ \end{cases} f(i,j)=⎩⎪⎨⎪⎧​1−p1​p2​f(i,i)+p4​​j=11−p1​p2f(i,j−1)+p3​f(i−1,j−1)+p4​​2≤j≤k1−p1​p2f(i,j−1)+p3​f(i−1,j−1)​j≥k+1​

• 会发现有环存在，不能递推，要解方程。但是发现构成环的都是 i i i相同的(从题目分析也能看出，总人数不变会一直循环)，但是环与环之间能递推(因为人数只会变少不会变多)。也就是说环内要解方程，环与环递推即可。
• 通过 f ( 1 , 1 ) = p 2 f ( 1 , 1 ) + p 4 1 − p 1 f(1,1)=\frac{p_2f(1,1)+p_4}{1-p_1} f(1,1)=1−p1​p2​f(1,1)+p4​​，求出初始值.
  因为环与环之间递推，所以在算 f ( i , j ) f(i,j) f(i,j)时， f ( i − 1 , j − 1 ) f(i-1,j-1) f(i−1,j−1)都求出来了，所以上面式子 f ( i − 1 , j − 1 ) f(i-1,j-1) f(i−1,j−1)项和常数项都当成已知，他们的和用 C C C数组表示，用 P P P表示 p 2 1 − p 1 \frac{p_2}{1-p_1} 1−p1​p2​​
  { f ( i , 1 ) = P f ( i , i ) + C ( 1 ) f ( i , 2 ) = P f ( i , 1 ) + C ( 2 ) f ( i , 3 ) = P f ( i , 2 ) + C ( 3 ) . . . f ( i , i − 1 ) = P f ( i , i − 2 ) + C ( i − 1 ) f ( i , i ) = P f ( i , i − 1 ) + C ( i ) ( 1 ) \begin{cases} f(i,1)=Pf(i,i)+C(1)\\ f(i,2)=Pf(i,1)+C(2)\\ f(i,3)=Pf(i,2)+C(3)\\ ...\\ f(i,i-1)=Pf(i,i-2)+C(i-1)\\ f(i,i)=Pf(i,i-1)+C(i)\quad (1)\\ \end{cases} ⎩⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎧​f(i,1)=Pf(i,i)+C(1)f(i,2)=Pf(i,1)+C(2)f(i,3)=Pf(i,2)+C(3)...f(i,i−1)=Pf(i,i−2)+C(i−1)f(i,i)=Pf(i,i−1)+C(i)(1)​
  从倒数第二项开始一直迭代到 ( 1 ) (1) (1)里面，得
  f ( i , i ) = P i ∗ f ( i , i ) + ∑ j = 0 i − 1 P j ∗ C ( i − j ) f ( i , i ) = 1 1 − P i ∗ ∑ j = 0 i − 1 P j ∗ C ( i − j ) \begin{aligned} f(i,i)&=P^i*f(i,i)+\sum_{j=0}^{i-1}P^j*C(i-j)\\ f(i,i)&=\frac{1}{1-P^i}*\sum_{j=0}^{i-1}P^j*C(i-j) \end{aligned} f(i,i)f(i,i)​=Pi∗f(i,i)+j=0∑i−1​Pj∗C(i−j)=1−Pi1​∗j=0∑i−1​Pj∗C(i−j)​
  然后再带到每个方程里。
  注意特判分母为0的情况

#include<stdio.h>
#define maxn 2005
double dp[maxn][maxn];
double x2_power[maxn];
double c[maxn];int main()
{int N,M,K;double p1,p2,p3,p4;while(scanf("%d%d%d",&N,&M,&K)!=EOF){scanf("%lf%lf%lf%lf",&p1,&p2,&p3,&p4);if(p1==1||p1+p2==1){printf("%.5lf\n",0);continue;}double x2,x3,x4;x2=p2/(1-p1);x3=p3/(1-p1);x4=p4/(1-p1);x2_power[0]=1.0;for(int i=1;i<maxn;i++)x2_power[i]=x2_power[i-1]*x2;dp[1][1]=x4/(1-x2);for(int i=2;i<=N;i++){c[1]=x4;for(int j=2;j<=K;j++)c[j]=x3*dp[i-1][j-1]+x4;for(int j=K+1;j<=i;j++)c[j]=x3*dp[i-1][j-1];double C=0;for(int j=1;j<=i;j++)C+=c[j]*x2_power[i-j];dp[i][i]=C/(1-x2_power[i]);dp[i][1]=dp[i][i]*x2+x4;for(int j=2;j<i;j++){dp[i][j]=x2*dp[i][j-1]+c[j];}}printf("%.5lf\n",dp[N][M]);}return 0;
}

本文标签： Activation