(Relax DP1.4)UVA 10648 Chocolate Box(求将n个巧克力放在m个盒子中的概率)

/*
 * UVA_10648.cpp
 *
 *  Created on: 2013年12月17日
 *      Author: Administrator
 */

#include 
  
   
#include 
   
     #include 
    
      using namespace std; const int maxn = 105; //dp[i][j]: 放了第i个巧克力时共有j个盒子中有巧克力的概率.. double dp[maxn][maxn]; int main(){ int n,m; int counter = 1; while(scanf("%d%d",&n,&m)!=EOF,n != -1){ memset(dp,0,sizeof(dp)); dp[1][1] = 1;//将1个巧克力放在1个盒子中的概率为1 int i,j; for(i = 2 ; i <= n ; ++i){ for(j = 1 ; j <= m ; ++j){ /** * dp[i-1][j]*j/m: 在放第i个巧克力的时候,已经有j个盒子中有巧克力了,所以第i个巧克力需要放在已经有巧克力的盒子中 * dp[i-1][j-1]*(m-j+1)/m: 在放第i个巧克力的时候,只有j个盒子中有巧克力。这是第i个巧克力需要放在没有巧克力的盒子中才能使有巧克力的盒子数达到j个 */ dp[i][j] = dp[i-1][j]*j/m + dp[i-1][j-1]*(m-j+1)/m; } } printf("Case %d: %.7lf\n",counter++,1-dp[n][m]); } return 0; }