[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的期望了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
}