題目大意:
n個巧克力,放在m個盒子裡,問至少有一個盒子是空的機率
題解:
dp[i][j]表示i個巧克力放到j個盒子裡的機率
dp[i][j]=dp[i-1][j]*1.0*j/m+dp[i-1][j-1]*1.0*(m-(j-1))/m;
dp[i-1][j] * j/m 第i個巧克力 放進了有巧克力的盒子裡。
dp[i-1][j-1] * (m-j+1)/m 第i個巧克力放進了其他空的盒子裡。
一開始覺得,至少一個盒子為空的機率,直接用1-盒子全部被占滿的機率,
![]()
UVA - 10648 Chocolate Box (機率dp) ,但是這麼計算出來的結果是不對的
比如有球A和B,A在那m個中選了,B随便進一個盒子,如果恰好和A進了同一個盒子
而第二次如果B在那m個中選了,A随便進一個盒子,如果恰好和B進了同一個盒子
這樣,兩種方法得出來的結果是一樣的,就會有重複
#include<bits/stdc++.h>
#include<cstring>
#define ll long long
#define INF 1000000007
#define eps 1e-7
using namespace std;
double dp[110][110];
int main()
{
//freopen("input.txt","r",stdin);
int n,m;
int cas=0;
while(~scanf("%d",&n))
{
if(n==-1)return 0;
scanf("%d",&m);//n個巧克力,m個盒子
dp[1][1]=1.0;
dp[1][0]=0.0;
for(int i=2;i<=n;++i)
for(int j=1;j<=m;++j)
if(j<=i)
dp[i][j]=dp[i-1][j]*1.0*j/m+dp[i-1][j-1]*1.0*(m-(j-1))/m;
double ans=0.0;
for(int i=1; i<m; ++i)
ans+=dp[n][i];
printf("Case %d: %.7f\n",++cas,ans);
}
return 0;
}