Codeforces 28C [概率DP]

/*
大连热身D题
题意:
有n个人,m个浴室每个浴室有ai个喷头,每个人等概率得选择一个浴室。
每个浴室的人都在喷头前边排队,而且每个浴室内保证大家都尽可能均匀得在喷头后边排队。
求所有浴室中最长队伍的期望。 思路:
概率dp dp[i][j][k]代表前i个浴室有j个人最长队伍是k的概率。
枚举第i个浴室的人数。然后转移的时候其实是一个二项分布。 */ #include<bits/stdc++.h>
using namespace std;
int jilu[];
double dp[][][];
double C[][];
void init() {
C[][] = ;
for ( int i = ; i <= ; i++ )
{
C[i][] = ;
for (int j = ; j <= i; j++)
C[i][j] = C[i-][j-] + C[i-][j];
}
}
int main()
{
int n,m;
init();
scanf("%d%d",&m,&n);
for(int i=;i<=n;i++)scanf("%d",jilu+i);
dp[][][]=;
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
for(int k=;k<=m;k++){
for(int c=;c<=j;c++){
if(c<=(k-)*jilu[i]){
dp[i][j][k]+=dp[i-][j-c][k]*C[j][c]/pow(i,j)*pow(i-,j-c);
}
else if(c<=k*jilu[i]){
for(int w=;w<=k;w++){
dp[i][j][k]+=dp[i-][j-c][w]*C[j][c]/pow(i,j)*pow(i-,j-c);
}
}
else break;
}
}
}
}
double ans=;
for(int i=;i<=m;i++){
ans+=i*dp[n][m][i];
}
printf("%.12lf\n",ans);
}
上一篇:【转】深度分析Java的ClassLoader机制(源码级别)


下一篇:HDU 4405 Aeroplane chess (概率DP)