Codeforces 28C Bath Queue 【计数类DP】*

时间：2022-03-02 01:55:17

Codeforces 28C Bath Queue

LINK

简要题意：有 n 个人等概率随机进入 m 个房间，一个房间可以有多个人，第 i 个房间有 ai 个水龙头，在一个房间的人要去排队装水，他们会使得最长的队尽可能小，求所有房间中最长队列长度的期望

Mark一个很好的blog

Codeforces 28C Bath Queue 【计数类DP】*

 #include<bits/stdc++.h>

 using namespace std;

 #define N 110

 #define fu(a,b,c) for(int a=b;a<=c;++a)

 #define fd(a,b,c) for(int a=b;a>=c;--a)

 double dp[N][N][N]={};

 double c[N][N]={};

 int a[N],n,m;

 int main(){

     scanf("%d%d",&n,&m);

     fu(i,,m)scanf("%d",&a[i]);

     fu(i,,n+m)c[i][]=;

     fu(i,,n+m)

         fu(j,,i)

             c[i][j]=c[i-][j-]+c[i-][j];

     fu(i,,m)dp[i][][]=;

     fu(i,,m)

         fu(j,,n)

             fu(k,,j){

                 //case1: 当前的房间到达上线

                 int l=max(a[i]*(k-)+,),r=a[i]*k;

                 fu(w,,k)

                     fu(p,l,min(r,j))

                         dp[i][j][k]+=dp[i-][j-p][w]*c[n-j+p][p];

                 //case2: 前面某个房间到达上限

                 fu(p,,min(l-,j))

                     dp[i][j][k]+=dp[i-][j-p][k]*c[n-j+p][p];

             }

     double ans=;

     fu(i,,n)ans+=dp[m][n][i]*i;

     fu(i,,n)ans/=(double)m;

     printf("%.10lf",ans);

     return ;

 }

相关文章