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} \]

结束。