题目

 

 

分析

数学期望

用$ dp[i][j] $表示发现了在$ j $个子系统里面发现了$ i $个bug到$ s $个子系统里面发现了$ n $个bug需要的期望天数。

$ dp[0][0] $就是答案。

然后分类一下，可以转移到$ dp[i][j] $无非就是$ dp[i+1][j+1] $ $ dp[i][j+1] $ $ dp[i+1][j] $ $ dp[i][j] $

各自分别算一下概率，比如从$ dp[i][j] $转移过来的话概率是$ \frac{i}{n} \times \frac{j}{s} $因为这天要刚好落在已经选择过的$ i $个bug和$ j $个子系统里。

其他的也差不多。

   

代码

由于日常include <bits/stdc++.h>所以poj的ce数量超级多。。。。。

1 // #include 
      
        2 #include 
       
         3 #include 
        
          4 using namespace std; 5 const int maxn=1050; 6 double dp[maxn][maxn]; 7 int main(){ 8     double n,s; scanf("%lf%lf",&n,&s); 9     memset(dp,0,sizeof(dp));10     for(int i=n;i>=0;i--)11         for(int j=s;j>=0;j--){12             if(i==n&&j==s) continue;13             double p1=i*j/n/s,p2=i*(s-j)/n/s,p3=(s-j)*(n-i)/n/s,p4=(n-i)*j/n/s;14             dp[i][j]=(1+p2*dp[i][j+1]+p3*dp[i+1][j+1]+p4*dp[i+1][j])/(1-p1);15         }16     printf("%.5f\n",dp[0][0]);17     return 0;18 }