uva 10648(简单dp)
Recently one of my friend Tarik became a member of the food committee of an ACM regional competition. He has been given m distinguishable boxes, he has to put n types of chocolates in the boxes. The probability that one chocolate is placed in a certain box is 1/m. What is the probability that one or more boxes are empty? At first he thought it as an easy task. But soon he found that it was much harder. So, he falls into a great trouble and asked you to help him in this task. Input Each line of the input contains two integers n indicating total number of distinguishable types of chocolate and m indicating total number of distinguishable boxes (m ≤ n < 100). A single line containing ‘-1’ denotes the end. Output For each of the cases you should calculate the probability corrected to seven decimal places. The output format is shown below.
Sample Input
50 12
50 12
-1
Sample Output
Case 1: 0.1476651
Case 2: 0.1476651
思路:题目要求一个或者 多个盒子为空的概率,可以先求所有盒子都不为空的概率;
设dp[i][j]为i个巧克力放入j个盒子的概率;
分为两种情况:1)前i-1个巧克力放入了j个盒子:则第i个就放入前j个盒子;
2)前i-1个巧克力放入了j-1个盒子:则第i个就放入剩下的m-(j-1)个盒子;
状态转移公式为:dp[i][j]=dp[i-1][j]*f[j]+dp[i-1][j-1]*f[m-j+1];
f[i]为i/m;
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
#define PI 3.141592653589792128462643383279502
double dp[][];
int i,j,k,n,m;
double f[];
int main(){
//#ifdef CDZSC_June
// freopen("in.txt","r",stdin);
//#endif
//std::ios::sync_with_stdio(false);
k=;
while(cin>>n){
if(n==-) break;
cin>>m;
memset(dp,,sizeof(dp));
for(i=;i<=m;i++) f[i]=(double)i/m;
dp[][]=;
for(i=;i<=n;i++)
for(j=;j<=m;j++){
dp[i][j]=dp[i-][j]*f[j]+dp[i-][j-]*f[m-j+];
}
printf("Case %d: %.7lf\n",++k,-dp[n][m]);
}
return ;
}
最新文章
- js中用tagname和id获取元素的3种方法
- Hbase Java API详解
- myeclipse项目里有红色感叹号
- reactjs入门到实战(二)---- jxs详解
- MySQL 5.1.73升级为MySQL 5.5.35详解
- 【linux】之虚拟机的使用
- 为 vsftpd 启动 vsftpd:500 OOPS: bad bool value in config file for: pasv_enable
- java读XML文件
- 你需要知道的九大排序算法【Python实现】之归并排序
- Spring 学习笔记01
- java提高篇(十四)-----关键字final
- require 增量更新与版本管理
- Java入门篇(五)——Java的字符串/String类
- 解决微信小程序video属性controls失效问题
- java.lang.IllegalStateException: LifecycleProcessor not initialized - call &#39;refresh&#39; before invoking lifecycle methods via the context: Root WebApplicationContext: startup date [Mon Oct 01 16:32:37 CS
- tensorFlow入门实践(三)实现lenet5(代码结构优化)
- Delphi之Exception获得错误信息
- web应用与http协议
- 【题解】Luogu CF915E Physical Education Lessons
- 20181014xlVBA获取小题零分名单