POJ 2096 Collecting Bugs——期望dp

POJ 2096 Collecting Bugs——期望dp

题意：

s个箱子，每个箱子里有无限个球，这些球有n种颜色。每天选择一个箱子，然后从箱子中拿一个球（每个箱子被选的概率为1/s,从这个箱子中拿出某种颜色球的概率为1/n）,问拿出的球有n种颜色且每个箱子都被选择过的天数期望

思路：

定义dp[i][j]为拿出的球有i种颜色且选择过j个箱子的天数期望

dp[i][j]可以转移到dp[i][j], dp[i][j+1], dp[i+1][j], dp[i+1][j+1],概率分别为(i/n)*(j/s), (i/n)*(1-j/s), (1-i/n)(j/s), (1-i/n)(1-j/s);

#include #include #include #include using namespace std;const int maxn = 1010;double dp[maxn][maxn];int n, s;int main() { scanf("%d%d", &n, &s); dp[n][s] = 0; for (int i = n; i >= 0; i--) { for (int j = s; j >= 0; j--) { if (i == n && j == s) continue; dp[i][j]=(i*(s-j)*dp[i][j+1]+(n-i)*j*dp[i+1][j]+(n-i)*(s-j)*dp[i+1][j+1]+n*s)/(n*s-i*j); } } printf("%.4f\n", dp[0][0]); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。