POJ2096 期望DP

题目传送门

简要题面:

一个程序有n个子程序。有s种bug,每天能等概率随机在一个子程序中找到一个bug,如果一个子程序中的一种bug被找到了,再下一次这个子程序的这种bug被找到的概率依然不变。问期望至少需要多少天能在每个子程序中都至少找到一个bug,把每一种bug都最少找到一次。

简要题解

设$f[i][j]$表示已经在i个程序中找到bug,找到j种bug,离任务完成期望还需要的天数。
显然$f[n][s]=0$,我们要求$f[0][0]$。
$$f[x][y]=\frac{xy}{ns}f[x][y]+\frac{(n-x)y}{ns}f[x+1][y]+\frac{x(s-y)}{ns}f[x][y+1]+\frac{(n-x)(s-y)}{ns}f[x+1][y+1]+1$$
右边的$f[x][y]$减到左边得
$$\frac{ns-xy}{ns}f[x][y]=\frac{(n-x)y}{ns}f[x+1][y]+\frac{x(s-y)}{ns}f[x][y+1]+\frac{(n-x)(s-y)}{ns}f[x+1][y+1]+1$$
把左边f[x][y]的系数除到右边得

$$
\begin{align}
f[x][y] & = \frac{ns}{ns-xy}(\frac{(n-x)y}{ns}f[x+1][y]+\frac{x(s-y)}{ns}f[x][y+1]+\frac{(n-x)(s-y)}{ns}f[x+1][y+1]+1) \\
& = \frac{ns}{ns-xy} \frac{(n-x)y f[x+1][y]+x(s-y)f[x][y+1]+(n-x)(s-y)f[x+1][y+1]+ns}{ns} \\
& = \frac{(n-x)y f[x+1][y]+x(s-y)f[x][y+1]+(n-x)(s-y)f[x+1][y+1]+ns}{ns-xy}
\end{align}
$$

结束。

文章目录
  1. 1. 简要题面:
  2. 2. 简要题解
|

博客使用Disqus作为评论系统