HDUOJ 4089 - Activation

题面

NN 个玩家要激活某种游戏,然而游戏的激活服务器对于这 NN 个玩家的激活请求只能一个一个处理(初始时主角 Tomato 排在第 MM)。

对于队列中的第一个人,激活时可能遇到一下四种情况:

  • 激活失败:队列不变,服务器将再次尝试激活当前玩家(概率 PactFailP_\text{actFail});
  • 连接失败:当前玩家被扔至队尾(概率 PconnLostP_\text{connLost});
  • 激活成功:当前玩家离开队列(概率 PactSuccessP_\text{actSuccess});
  • 服务中断:服务器炸了,无符继续处理任何请求(概率 PdownP_\text{down})。

求服务器服务中断并且此时 Tomato 排名 K\leq K 的概率(后文中记该事件为事件 AA)。

数据范围

1MN20001 \le M \le N \le 2000

题目链接

分析

我们用 dp[i][j]dp[i][j] 来表示队列长度为 ii 且 Tomato 排在第 jj 时事件 AA 发生的概率。那么很显然,我们所要求的就是 dp[N][M]dp[N][M]

如何进行状态转移?我们不难推出:

dp[i][j]={PactFaildp[i][1]+PconnLostdp[i][i]+Pdownj=1PactFaildp[i][j]+PconnLostdp[i][j1]+PactSuccessdp[i1][j1]+Pdown2jkPactFaildp[i][j]+PconnLostdp[i][j1]+PactSuccessdp[i1][j1]j>kdp[i][j] =
\begin{cases}
P_\text{actFail} dp[i][1] + P_\text{connLost} dp[i][i] + P_\text{down} & j =1 \
P_\text{actFail} dp[i][j] + P_\text{connLost} dp[i][j - 1] + P_\text{actSuccess} dp[i - 1][j - 1] + P_\text{down} & 2 \le j \le k \
P_\text{actFail} dp[i][j] + P_\text{connLost} dp[i][j - 1] + P_\text{actSuccess} dp[i - 1][j - 1] & j > k \
\end{cases}

接下来我们对其进行化简:

dp[i][j]={PconnLostdp[i][i]+Pdown1PactFailj=1PconnLostdp[i][j1]+PactSuccessdp[i1][j1]+Pdown1PactFail2jkPconnLostdp[i][j1]+PactSuccessdp[i1][j1]1PactFailj>kdp[i][j] =
\begin{cases}
\frac{P_\text{connLost}dp[i][i] + P_\text{down}}{1 - P_\text{actFail}} & j =1 \
\frac{P_\text{connLost}dp[i][j - 1] + P_\text{actSuccess}dp[i - 1][j - 1] + P_\text{down}}{1 - P_\text{actFail}} & 2 \le j \le k \
\frac{P_\text{connLost}dp[i][j - 1] + P_\text{actSuccess}dp[i - 1][j - 1]}{1 - P_\text{actFail}} & j > k \
\end{cases}

为了方便,我们不妨记:

PconnLost=PconnLost1PactFailPactSuccess=PactSuccess1PactFailPdown=Pdown1PactFail\begin{aligned}
P_\text{connLost}’ & = \frac{P_\text{connLost}}{1 - P_\text{actFail}} \
P_\text{actSuccess}’ & = \frac{P_\text{actSuccess}}{1 - P_\text{actFail}} \
P_\text{down}’ & = \frac{P_\text{down}}{1 - P_\text{actFail}} \
\end{aligned}

因此,转移方程被进一步化简为:

dp[i][j]={PconnLostdp[i][i]+Pdownj=1PconnLostdp[i][j1]+PactSuccessdp[i1][j1]+Pdown2jkPconnLostdp[i][j1]+PactSuccessdp[i1][j1]j>kdp[i][j] =
\begin{cases}
P_\text{connLost}‘dp[i][i] + P_\text{down}’ & j =1 \
P_\text{connLost}'dp[i][j - 1] + P_\text{actSuccess}‘dp[i - 1][j - 1] + P_\text{down}’ & 2 \le j \le k \
P_\text{connLost}'dp[i][j - 1] + P_\text{actSuccess}'dp[i - 1][j - 1] & j > k \
\end{cases}

好的,现在我们已经解决了转移方程的问题,接下来要考虑的是该怎么写代码咯。

观察转移方程,不难发现如果我们从 i=1Ni = 1 \rightarrow N 进行递推的话,当我们在计算 dp[i]dp[i]dp[i1]dp[i - 1] 事实上全是常量。因此,方程中除了含 PconnLostP_\text{connLost}' 的一项,剩余项均可看作常数项。

我们不妨将第 jj 个式子的常数项记作 c[j]c[j],因此在计算 dp[i]dp[i] 时相当于求解 ii 元一次方程组:

{dp[i][1]=PconnLostdp[i][i]+c[1]dp[i][2]=PconnLostdp[i][1]+c[2]...dp[i][i]=PconnLostdp[i][i1]+c[i]\begin{cases}
dp[i][1] & = P_\text{connLost}'dp[i][i] + c[1] \
dp[i][2] & = P_\text{connLost}'dp[i][1] + c[2] \
… \
dp[i][i] & = P_\text{connLost}'dp[i][i - 1] + c[i] \
\end{cases}

ii 元一次方程组小学生都会解……

dp[i][i]=PconnLostdp[i][i1]+c[i]=PconnLost(PconnLostdp[i][i2]+c[i1])+c[i]= ...=PconnLosti1dp[i][1]+PconnLosti2c[2]+...+PconnLostc[i1]+c[i]=PconnLostidp[i][i]+PconnLosti1c[1]+...+PconnLostc[i1]+c[i]\begin{aligned}
dp[i][i] & = P_\text{connLost}‘dp[i][i - 1] + c[i] \
& = P_\text{connLost}’(P_\text{connLost}‘dp[i][i - 2] + c[i - 1]) + c[i] \
& = \ … \
& = {P_\text{connLost}’}^{i - 1}dp[i][1] + {P_\text{connLost}’}^{i - 2}c[2] + … + P_\text{connLost}c[i - 1] + c[i] \
& = {P_\text{connLost}’}^{i}dp[i][i] + {P_\text{connLost}’}^{i - 1}c[1] + … + P_\text{connLost}c[i - 1] + c[i] \
\end{aligned}

化简,得:

dp[i][i]=j=1i(PconnLostijc[j])1PconnLostidp[i][i] = \frac{\sum\limits_{j = 1}{i}({P_\text{connLost}'}{i - j} \cdot c[j])}{1 - {P_\text{connLost}’}^{i}}

然后剩下的变量只需要递推求解一下就行咯。

接下来我们剩下的唯一问题就是 c[j]c[j] 具体是什么了。我们也不难看出:

c[j]={Pdownj=1PactSuccessdp[i1][j1]+Pdown2jkPactSuccessdp[i1][j1]j>kc[j] =
\begin{cases}
P_\text{down}’ & j = 1 \
P_\text{actSuccess}‘dp[i - 1][j - 1] + P_\text{down}’ & 2 \le j \le k \
P_\text{actSuccess}'dp[i - 1][j - 1] & j > k
\end{cases}

最后要注意的是,如果 Pdown=0P_\text{down} = 0,那概率肯定是 00 啦,还算个毛线~

有了上述分析,我们就可以很容易地用递推写出代码了。

实现

像我这种智商欠费的🐷在写概率 DP 时还是不要为了省一点空间作死下标从 00 开始了…… 😭

完整参考代码

%%%

This blog is under a CC BY-NC-SA 4.0 Unported License.
Link to this article: https://blog.codgician.pw/2018/02/17/hduoj-4089/