题目描述
输入
输出
样例输入
1 2
样例输出
3.0000
题目大意
共有n种bug和s个系统，每天随机发现1个系统中的1种bug，问：发现所有种类的bug，且每个系统都发现bug的期望天数。
题解
期望dp
f[i][j] = f[i+1][j+1]*(n-i)/n*(s-j)/s + f[i][j+1]*i/n*(s-j)/s + f[i+1][j]*(n-i)/n*j/s + f[i][j]*i/n*j/s + 1
移项，合并同类项，化简
1 #include <cstdio> 2 double f[1002][1002]; 3 int main() 4 { 5 int n , s , i , j; 6 scanf("%d%d" , &n , &s); 7 for(i = n ; i >= 0 ; i -- ) 8 for(j = s ; j >= 0 ; j -- ) 9 if(i != n || j != s) 10 f[i][j] = (f[i + 1][j + 1] * (n - i) * (s - j) + f[i][j + 1] * i * (s - j) + f[i + 1][j] * (n - i) * j + (n * s)) / (n * s - i * j); 11 printf("%.4lf\n" , f[0][0]); 12 return 0; 13 }
原文：http://www.cnblogs.com/GXZlegend/p/6200476.html