[POJ2096] Collecting Bugs （期望, DP）

链接：https://cn.vjudge.net/problem/POJ-2096

有一个程序员要在 $s$ 个子系统里找 $n$ 个不同的BUG，问在 $s$ 种子系统里找到 $n$ 个BUG的天数期望。

这题是求期望的入门经典，我想拿这道题来做一个总结。

首先是最重要的、也就是期望的一些性质：

1：当 $X$ 和 $Y$ 两个并不一定相互独立随机变量时，我们有如下性质：

$E(aX+bY)=aE(X)+bE(Y)$
上述性质称为期望的线性性（可加性），证明很容易，略。

2：全期望公式：

$E(Y)=E(E(Y|X))=\sum_{i}P(X=x_i)E(Y|X=x_i)$
当期望存在条件时，可以类比全概率公式获得全期望公式。

以及解决期望问题的常用方法：

解决期望问题有两种方法：高斯消元或者DP。

1：高斯消元不必多说，我们根据题意枚举出所有状态，并根据状态列出期望方程组，使用高斯消元求得各个状态的期望解。

2：当所求状态的期望之间存在一定关系的时候，可以使用动态规划解决期望问题：首先做的事自然是找准递推状态，这是肯定的。找到状态后，接下来要枚举出所有的状态转移，同时计算出转移的条件和代价。我们描述一下上述步骤执行后应该得到的结果：状态 $i$ 、状态 $i$ 下的期望 $E(i)$ 、状态 $i$ 下的递推状态 $(j|j由i转移得到)$ ，每一种状态转移所需的代价 $w_i$ 。

我们可以由状态i下递推出来的状态j获得i状态的期望： $\sum w_jE(j)$ 。我们利用期望的可加性，就可以得到 $i$ 的期望了。

对于本题，我们可以设 $f(i,j)$ 表示在 $j$ 个系统中找到 $i$ 个BUG后期望天数。很明显，当 $n$ 天 $s$ 个系统中找到BUG后，该天的期望 $E(n,s)=0$ 。

接下来我们以找到一个BUG为转移条件，由 $(i,j)$ 可以转移出四个不同的状态：

$(i,j)$ 表示在 $j$ 个系统中没有再找到新BUG，转移代价为 $p_1=\frac{i}{n} × \frac{j}{s}$ 。

$(i+1,j)$ 表示在 $j$ 个系统中找到了一个新BUG，转移代价为 $p_2=\frac{n-i}{n} × \frac{j}{s}$ 。

$(i,j+1)$ 表示在一个新系统中找到了一个已有BUG，转移代价为 $p_3=\frac{i}{n} × \frac{s-j}{s}$ 。

$(i+1,j+1)$ 表示在一个新系统中找到了一个新BUG，转移代价为 $p_4=\frac{n-i}{n} × \frac{s-j}{s}$ 。

我们可以列出状态 $(i,j)$ 的期望等式：

$E(i,j)=p_1E(i,j)+p_2E(i+1,j)+p_3E(i,j+1)+p_4E(i+1,j+1)$
移项得：

$E(i,j)=\frac{p_2E(i+1,j)+p_3E(i,j+1)+p_4E(i+1,j+1)}{1-p_1}$
我们由

$(n,s)$ 倒着递推，递推到

$(0,0)$ 时即为要在s个系统中找到n个BUG的期望了。

const int maxn = 1010;
double f[maxn][maxn];
int n, s;

signed main() {
  // freopen("in", "r", stdin);
  while(~scanf("%d%d",&n,&s)) {
    f[n][s] = 0;
    double q = n * s;
    for(int i = n; i >= 0; i--) {
      for(int j = s; j >= 0; j--) {
        if(i == n && j == s) continue;
        double p1 = double(i * j) / q;
        double p2 = double((n - i) * j) / q;
        double p3 = double(i * (s - j)) / q;
        double p4 = double((n - i) * (s - j)) / q;
        f[i][j] = (p2*f[i+1][j]+p3*f[i][j+1]+p4*f[i+1][j+1]+1.)/(1.0-p1);
      }
    }
    printf("%.4f\n", f[0][0]);
  }
  return 0;
}