「 poj 2096 」 Collecting Bugs

先说一下题意

$s$ 个子系统还中有 $n$ 种 $\text{bug}$，每天可以随机选择一种 $\text{bug}$，问选出 $n$ 种 $\text{bug}$ 在 $s$ 种子系统中的期望天数。

 

解题思路

不妨设 $dp[i][j]$ 表示在选择 $i$ 种 $\text{bug}$，$j$ 种子系统的期望天数。

那么新选择的 $\text{bug}$ 就会出现一下四种情况

新发现的 $\text{bug}$ 在已经发现的 $i$ 种 $\text{bug}$中，已经发现的 $j$ 个子系统中，概率是 $p1=\frac{i}{n} \times \frac{j}{s}$新发现的 $\text{bug}$ 在已经发现的 $i$ 种 $\text{bug}$中，但却在新的子系统里，概率是 $p2=\frac{i}{n} \times \frac{s-j}{s}$新发现的 $\text{bug}$ 是新的 $\text{bug}$，但却在已经发现的子系统里，概率是 $p3=\frac{n-i}{n} \times \frac{j}{s}$新发现的 $\text{bug}$ 是新的 $\text{bug}$，也在新的子系统中,概率是 $p4=\frac{n-i}{n} \times \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\n", dp[0][0]); } }

 

转载于:https://www.cnblogs.com/bljfy/p/9602448.html

相关资源：数据结构—成绩单生成器