首页 > 代码库 > poj 2096 Collecting Bugs

poj 2096 Collecting Bugs

2024-07-15 01:33:53   215人阅读

题意：

一个新项目里面，有n种bugs,有s 个subcomponents，

找出的一个bug属于n个bugs里的某一种的概率为 1/n;

找出的一个bug属于m个subcomponentsde里的某一种的概率为 1/m

求每种bugs至少找出一个bug，每种subcomponents找出一个bug的次数期望

dp[n][s]=0

dp[i][j]——》dp[i][j]    概率为i/n*j/s

dp[i][j]——》dp[i+1][j]    概率为(n-i)/n*j/s

dp[i][j]——》dp[i][j+1]    概率为i/n*(s-j)/s

dp[i][j]——》dp[i+1][j+1]    概率为(n-i)/n*(s-j)/s

所以：dp[i][j]=(1.0+dp[i+1][j]*1.0*(n-i)/n*j/s+dp[i][j+1]*1.0*i/n*(s-j)/s+dp[i+1][j+1]*1.0*(n-i)/n*(s-j)/s)/(1-1.0*i/n*j/s);

 1 #include<iostream> 2 #include<string.h> 3 #include<algorithm> 4 #include<stdio.h> 5 using namespace std; 6 double dp[1010][1010]; 7 int main(){ 8     int n,s; 9     while(cin>>n>>s){10         dp[n][s]=0;11         for(int i=n;i>=0;i--)12             for(int j=s;j>=0;j--){13                 if(i==n&&j==s) continue;14                 dp[i][j]=(1.0+dp[i+1][j]*1.0*(n-i)/n*j/s+dp[i][j+1]*1.0*i/n*(s-j)/s+dp[i+1][j+1]*1.0*(n-i)/n*(s-j)/s)/(1-1.0*i/n*j/s);15             }16         printf("%.7f\n",dp[0][0]);17     }18 19 }

 


联系
我们