先说一下题意
$s$ 个子系统还中有 $n$ 种 $ ext{bug}$，每天可以随机选择一种 $ ext{bug}$，问选出 $n$ 种 $ ext{bug}$ 在 $s$ 种子系统中的期望天数。
解题思路
不妨设 $dp[i][j]$ 表示在选择 $i$ 种 $ ext{bug}$，$j$ 种子系统的期望天数。
那么新选择的 $ ext{bug}$ 就会出现一下四种情况
- 新发现的 $ ext{bug}$ 在已经发现的 $i$ 种 $ ext{bug}$中，已经发现的 $j$ 个子系统中，概率是 $p1=frac{i}{n} imes frac{j}{s}$
- 新发现的 $ ext{bug}$ 在已经发现的 $i$ 种 $ ext{bug}$中，但却在新的子系统里，概率是 $p2=frac{i}{n} imes frac{s-j}{s}$
- 新发现的 $ ext{bug}$ 是新的 $ ext{bug}$，但却在已经发现的子系统里，概率是 $p3=frac{n-i}{n} imes frac{j}{s}$
- 新发现的 $ ext{bug}$ 是新的 $ ext{bug}$，也在新的子系统中,概率是 $p4=frac{n-i}{n} imes frac{s-j}{s}$
稍微推一下就能够得到状态转移方程。
附上代码
#include <iostream> #include <cstring> #include <cstdio> using namespace std; int n, s; double dp[1003][1003], p1, p2, p3, p4; int main() { while (scanf("%d%d", &n, &s) == 2) { memset(dp, 0, sizeof(dp)); for(int i=n; i>=0; i--) { for(int j=s; j>=0; j--) { if(i == n && j == s) continue; p1 = 1.0 * i/n * j/s; p2 = 1.0 * i/n * (s-j)/s; p3 = 1.0 * (n-i)/n * j/s; p4 = 1.0 * (n-i)/n * (s-j)/s; dp[i][j] = (dp[i][j+1]*p2 + dp[i+1][j]*p3 + dp[i+1][j+1]*p4 + 1.0) / (1.0-p1); } } printf("%.4lf ", dp[0][0]); } }