有生以来见过的最恶心的DP题目。


题意:n个人排队激活仙剑奇侠5.服务器会按队列顺序进行激活操作。但是在激活队首顾客时,会有以下4中情况:

1.激活失败,重试:概率p1
2.链接丢失,队首顾客被扔到队尾:概率p2
3.激活成功:队首顾客消失
4.服务器错误:服务器被关闭,队列里的所有顾客的请求失效。

现在排在第m个的人想知道,有多大的可能性他前面有少于k个人时服务器关闭,因为这样是很操蛋的(原文是suck)


思路:很直接想到用f[i][j]表示有i个人排队站在第j个时出现suck情况的概率。那么...然后一阵沉默.

\begin{equation}
f[i][1]=f[i][1]P_1+f[i][i]P_2+P_4
\end{equation}
\begin{equation}
f[i][j]=f[i][j]P_1+f[i][j-1]P_2+f[i-1][j-1]P_3 (j>k)
\end{equation}
\begin{equation}
f[i][j]=f[i][j]P_1+f[i][j-1]P_2+f[i-1][j-1]P_3+P_4 (j<=k)
\end{equation}

移项。

令$P_{21}=\frac{P_2}{1-P_1}$,$P_{31}=\frac{P_3}{1-P_1}$,$P_{41}=\frac{P_4}{1-P_1}$

设一个数组C[]

\begin{equation}
\left{
\begin{aligned}
C[j]=f[i-1][j-1]P_{31}(j>k) \\
C[j]=f[i-1][j-1]P_{31}+P_{41}(j<=k) \\
\end{aligned}
\right.
\end{equation}

那么

\begin{equation}
f[i][1]=f[i][i]P_{21}+P_{41}
\end{equation}
\begin{equation}
f[i][j]=f[i][j-1]P_{21}+C[j]
\end{equation}

这样我们就可以递推了

吗?

由于f[i][1]和f[i][i]互相依赖,所以呵呵。

于是我们得手动列出f[i][j]的表达式,手动代入消元

然后可以得到:

\begin{equation}
f[i][i]=\frac{\sum{P_{21}^{i-x}C[x]}{x=1}^{i}}{1-P{21}^i}
\end{equation}

然后就可以用f[i][i]开始递推了