题意：
一个新项目里面，有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 }
poj 2096 Collecting Bugs,布布扣,bubuko.com
原文：http://www.cnblogs.com/ainixu1314/p/3880704.html