CF28C Bath Queue 概率DP

    科技2022-07-20  132

    文章目录

    一.题目二.Solution三.CodeThanks!

    一.题目

    n ( 1 ≤ n ≤ 50 ) n(1≤n≤50) n(1n50)个学生同时洗衣服,有 m ( 1 ≤ m ≤ 50 ) m(1≤m≤50) m(1m50)个洗衣房,第i个洗衣房里有 a i ( 1 ≤ a i ≤ 50 ) a_i(1≤a_i≤50) ai(1ai50)台洗衣机。 每个学生会从 m m m个洗衣房里随机选择一个,选择同一个洗衣房的学生会按照房间里洗衣机的数量平均排队,求最长队列人数的期望。 例如:有3个人选择了1号房间有2台洗衣机,9个人选择了2号房间有3台洗衣机,此时1号房间内最长队列长度为2,2号房间内最长队列长度为3,所以这个状态的最长队列长度为3。 传送门

    二.Solution

    这道题是一道典型的概率DP,这里可以把期望看成带权概率。

    定义 d p [ i ] [ j ] [ l ] dp[i][j][l] dp[i][j][l]为已安排了前i个房间和j个人,最长的排队队伍为l的概率,最后的时候对于每个 d p [ m ] [ n ] [ l ] dp[m][n][l] dp[m][n][l]再乘上一个 l l l就行了,初始值 d p [ i ] [ 0 ] [ 0 ] = 1 dp[i][0][0]=1 dp[i][0][0]=1显而易见。

    然后开始推转移方程式,这里我们大力分类讨论: 1.当前的第i个房间的最长队伍就为l: 这样一来就不管后面的人怎么排,我们只要挑出能使当前第i个房间的最长队伍为l的人数就行了,这个人数有最大值和最小值,即: a [ j ] ∗ ( l − 1 ) + 1 ≤ p ≤ a [ j ] ∗ l a[j]*(l-1)+1\leq p\leq a[j]*l a[j](l1)+1pa[j]l挑人的时候要用到组合数。 于是就有递推式: ∑ k = 0 l ∑ p = a [ j ] ∗ ( l − 1 ) + 1 a [ j ] ∗ l C n − j + p p ∗ d p [ i − 1 ] [ j − p ] [ k ] \sum_{k=0}^{l}\sum_{p=a[j]*(l-1)+1}^{a[j]*l}C_{n-j+p}^{p}*dp[i-1][j-p][k] k=0lp=a[j](l1)+1a[j]lCnj+ppdp[i1][jp][k] 2.当前的第i个房间的最长队伍小于l: 显而易见,我们的人数范围: 0 ≤ p ≤ a [ j ] ∗ ( l − 1 ) 0\leq p\leq a[j]*(l-1) 0pa[j](l1)加上组合数枚举就行了: ∑ p = 0 a [ j ] ∗ ( l − 1 ) C n − j + p p ∗ d p [ i − 1 ] [ j − p ] [ l ] \sum_{p=0}^{a[j]*(l - 1)}C_{n-j+p}^{p}*dp[i-1][j-p][l] p=0a[j](l1)Cnj+ppdp[i1][jp][l] 最后把两个递推式合起来就是完整的递推式了: d p [ i ] [ j ] [ l ] = ∑ k = 0 l ∑ p = a [ j ] ∗ ( l − 1 ) + 1 a [ j ] ∗ l C n − j + p p ∗ d p [ i − 1 ] [ j − p ] [ k ] + dp[i][j][l]=\sum_{k=0}^{l}\sum_{p=a[j]*(l-1)+1}^{a[j]*l}C_{n-j+p}^{p}*dp[i-1][j-p][k]+ dp[i][j][l]=k=0lp=a[j](l1)+1a[j]lCnj+ppdp[i1][jp][k]+ ∑ p = 0 a [ j ] ∗ ( l − 1 ) C n − j + p p ∗ d p [ i − 1 ] [ j − p ] [ l ] \sum_{p=0}^{a[j]*(l - 1)}C_{n-j+p}^{p}*dp[i-1][j-p][l] p=0a[j](l1)Cnj+ppdp[i1][jp][l] 所以期望的题一般可以转换成概率题,概率题初始值为1然后推就完了。

    三.Code

    #include <cstdio> #include <cstring> #include <iostream> #include <cmath> using namespace std; #define M 55 #define INF 0x7f7f7f7f int n, m, a[M]; double dp[M][M][M], C[M][M], ans; int main (){ scanf ("%d %d", &n, &m); for (int i = 1; i <= m; i ++) scanf ("%d", &a[i]); for (int i = 0; i <= n; i ++){ C[i][i] = C[i][0] = 1; for (int j = 1; j < i; j ++) C[i][j] = C[i - 1][j - 1] + C[i - 1][j]; } dp[0][0][0] = 1; for (int i = 1; i <= m; i ++){ dp[i][0][0] = 1; for (int j = 1; j <= n; j ++){ for (int l = 0; l <= n; l ++){ int maxn = l * a[i], minn = (l - 1) * a[i] + 1; for (int k = 0; k <= l; k ++){ for (int p = max (minn, 0); p <= maxn && p <= j; p ++){ dp[i][j][l] += dp[i - 1][j - p][k] * C[n - j + p][p]; } } for (int k = 0; k < minn && k <= j; k ++) dp[i][j][l] += dp[i - 1][j - k][l] * C[n - j + k][k]; } } } for (int i = 1; i <= n; i ++) ans += dp[m][n][i] * i;//带权 printf ("%.10f\n", ans / pow (m, n)); return 0; }

    Thanks!

    Processed: 0.030, SQL: 8