题目大意：有n种bug，m个程序，小明每天能找到一个bug。每次bug出现的种类和所在程序都是等机会均等的，并且默认为bug的数目无限多。如果要使每种bug都至少找到一个并且每个程序中都至少找到一个bug，小明平均需要找几天？

题目分析：定义状态dp(i,j)表示找到了 i 种程序，并且出现在了 j 个程序中还需要的平均时间。则状态转移方程为:

dp(i,j)=i/n*j/m*dp(i,j)+(n-i)/n*j/m*dp(i+1,j)+i/n*(m-j)/m*dp(i,j+1)+(n-i)/n*(m-j)/m*dp(i+1,j+1)+1。

逆推之。

 

ps：这道题的题意不好懂。。

 

代码如下：

# include
     
      # include
      
       # include
       
        # include
        
         using namespace std;int n,m;double dp[1005][1005];int main(){    while(~scanf("%d%d",&n,&m))    {        memset(dp,0,sizeof(dp));        for(int i=n;i>=0;--i){            for(int j=m;j>=0;--j){                if(i==n&&j==m) continue;                double right=(double(m-j)*i)/n/m;                double low=(double(n-i)*j)/n/m;                double rl=(double(n-i)*(m-j))/n/m;                double th=1.0-((double)(i*j))/n/m;;                dp[i][j]=right*dp[i][j+1]+low*dp[i+1][j]+rl*dp[i+1][j+1]+1;                dp[i][j]/=th;            }        }        printf("%.4lf\n",dp[0][0]);    }    return 0;}