首页 > 代码库 > Codeforces 28C [概率DP]
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[55]; double dp[55][55][55]; double C[55][55]; void init() { C[0][0] = 1; for ( int i = 1; i <= 50; i++ ) { C[i][0] = 1; for (int j = 1; j <= i; j++) C[i][j] = C[i-1][j-1] + C[i-1][j]; } } int main() { int n,m; init(); scanf("%d%d",&m,&n); for(int i=1;i<=n;i++)scanf("%d",jilu+i); dp[0][0][0]=1; for(int i=1;i<=n;i++){ for(int j=0;j<=m;j++){ for(int k=0;k<=m;k++){ for(int c=0;c<=j;c++){ if(c<=(k-1)*jilu[i]){ dp[i][j][k]+=dp[i-1][j-c][k]*C[j][c]/pow(i,j)*pow(i-1,j-c); } else if(c<=k*jilu[i]){ for(int w=0;w<=k;w++){ dp[i][j][k]+=dp[i-1][j-c][w]*C[j][c]/pow(i,j)*pow(i-1,j-c); } } else break; } } } } double ans=0; for(int i=1;i<=m;i++){ ans+=i*dp[n][m][i]; } printf("%.12lf\n",ans); }
Codeforces 28C [概率DP]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。