POJ2096 期望DP

题目传送门

简要题面:

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

简要题解

f[i][j]f[i][j]表示已经在i个程序中找到bug,找到j种bug,离任务完成期望还需要的天数。 显然f[n][s]=0f[n][s]=0,我们要求f[0][0]f[0][0]

f[x][y]=xynsf[x][y]+(nx)ynsf[x+1][y]+x(sy)nsf[x][y+1]+(nx)(sy)nsf[x+1][y+1]+1f[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]f[x][y]减到左边得

nsxynsf[x][y]=(nx)ynsf[x+1][y]+x(sy)nsf[x][y+1]+(nx)(sy)nsf[x+1][y+1]+1\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]的系数除到右边得

结束。

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

博客使用Disqus作为评论系统