poj 2096 Collecting Bugs （期望）

本文主要是介绍poj 2096 Collecting Bugs （期望），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

某个系统中有n个子系统和m个bug类型，该系统每天会出现一个bug （属于某个子系统和某个bug类型），bug的类型是等概率的，bug也是等概率地出现在每个子系统的。问所有子系统都出现bug且所有的bug类型都出现的期望天数。

Input

Input file contains two integer numbers, n and s (0 < n, s <= 1 000).

Output

Output the expectation of the Ivan's working days needed to call the program disgusting, accurate to 4 digits after the decimal point.

Sample Input

1 2

Sample Output

3.0000

我们用E(i,j)E(i,j)表示他找到了ii个bug和jj个子组件，离找到nn个bug和ss个子组件还需要的期望次数，这样要求的就是E(0,0)E(0,0)，而E(n,s)=0E(n,s)=0，对任意的E(i,j)E(i,j)。
1次查找4种情况：
1. 没发现任何新的bug和子组件
2. 发现一个新的bug
3. 发现一个新的子组件
4. 同时发现一个新的bug和子组件

#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
const int maxn=1005;
double dp[maxn][maxn];
int main()
{int n,s;cin>>n>>s;memset(dp,0,sizeof(dp));for(int i=n; i>=0; i--){for(int j=s; j>=0; j--){if(n==i&&s==j)continue;double tp=(1.0-(double)i*j/(n*s));dp[i][j]+=(double)(n-i)*j/(n*s)*dp[i+1][j];dp[i][j]+=(double)i*(s-j)/(n*s)*dp[i][j+1];dp[i][j]+=(double)(n-i)*(s-j)/(n*s)*dp[i+1][j+1];dp[i][j]+=1.0;dp[i][j]/=tp;}}printf("%.4f\n",dp[0][0]);return 0;
}

 

这篇关于poj 2096 Collecting Bugs （期望）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---