传送门
数据：
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
题意（原文）+（大意）
A bug found in the program can be of any category withequal probability. Similarly, the bug can be found in any given subsystem withequal probability.Any particular bugcannot belong to two different categoriesorhappen simultaneously in two different subsystems. The number of bugs in the program is almostinfinite, so the probability of finding a new bug of some category in some subsystem does not reduce after finding any number of bugs of that category in that subsystem.
Find anaverage time(in days of Ivan's work) required to name the program disgusting.
在程序中发现的一个bug可以是任何一类，概率相等。类似地，在任何给定的子系统中，同样有可能发现该错误。任何特定的bug不能属于两个不同的类别，也不能同时发生在两个不同的子系统中。程序中错误的数量几乎是无限的，因此在某个子系统中找到某个类别的新错误的概率在该子系统中找到该类别的任何数量的错误后不会降低。 找出一个平均时间(伊万工作的天数)来命名这个愤慨的节目。
题意：n种bug，s个子系统 每天都会发现一个bug，可能是任意子系统的任意一种bug，求找出这s个子系统中的n种bug需要天数的期望值；
思路：计算期望E=∑所有可能需要的天数*概率
dp[i][j]表示已经找到i种bug，j个系统里找到bug，离目标还需要的期望天数。
如果明天找到一种bug，有四种情况，转移情况：
dp[i+1][j]不属于i种，属于j个系统之一。概率为p1=(n-i)/n* j/s。
dp[i][j+1]属于i种之一，不属于j个系统。 概率为p2=(s-j)/s* i/n
dp[i+1][j+1] 不属于i种，不属于j个系统。 概率为p3=(n-i)/n*(s-j)/s
dp[i][j] 属于i种之一，属于j个系统之一。概率为p4=i/n* j/s
p1+p2+p3+p4=1，所以有下面这个式子。
dp[i][j]=dp[i+1][j]*p1+dp[i][j+1]*p2+dp[i+1][j+1]*p3+dp[i][j]*p4+1 --->状态转移
期望E=∑（昨天可以转移到现在状态的所有可能的情况的期望+1）*概率=∑（昨天可以转移到现在状态的所有可能的情况的期望）*概率 +1参考这个理解的
整理的：dp[i][j]= (n*s+(n-i)*j*dp[i+1,j]+i*(s-j)*dp[i,j+1]+(n-i)*(s-j)*dp[i+1,j+1])/(n*s-i*j)
知道dp[n][s]=0，就是已经到达目标，还需要0天。然后逆推。
数学期望：离散随机变量的一切可能值与其对应的概率P的乘积之和称为数学期望
注意：printf("%.4lf",ans); 正确的答案在G++下会wa；在C++下提交OK
code：
#include<stdio.h>#include<string.h>#include<algorithm>using namespace std;typedef long long ll;const int N=1e5+10;#define mem(a,b) memset(a,b,sizeof(a))double dp[1010][1010];int main(){int n,s;while(scanf("%d %d",&n,&s)!=EOF){mem(dp,0);for(int i=n; i>=0; i--){for(int j=s; j>=0; j--){if(i==n&&j==s)continue;double p1=(n-i)*(s-j)*1.0/(n*s)*1.0;double p2=i*(s-j)*1.0/(n*s)*1.0;double p3=(n-i)*j*1.0/(n*s)*1.0;double p4=i*j*1.0/(n*s)*1.0;dp[i][j]=(dp[i+1][j+1]*p1+dp[i][j+1]*p2+dp[i+1][j]*p3+1)/(1-p4);}}printf("%0.4f\n",dp[0][0]);}return 0;}
太难了太难了~dp关键在状态转移方程！加油！
如果觉得《Collecting Bugs（解决bug）》对你有帮助，请点赞、收藏，并留下你的观点哦！
