频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
(Relax DP1.4)UVA 10648 Chocolate Box(求将n个巧克力放在m个盒子中的概率)
2013-12-19 13:15:14         来源:黄俊东的专栏  
收藏   我要投稿
/*
 * 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;
}




点击复制链接 与好友分享!回本站首页
相关TAG标签 概率 盒子 巧克力
上一篇:HDU3863锛歂o Gambling
下一篇:LeetCode Sudoku Solver
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站