有 n ( 1 ≤ n ≤ 50 ) n(1≤n≤50) n(1≤n≤50)个学生同时洗衣服,有 m ( 1 ≤ m ≤ 50 ) m(1≤m≤50) m(1≤m≤50)个洗衣房,第i个洗衣房里有 a i ( 1 ≤ a i ≤ 50 ) a_i(1≤a_i≤50) ai(1≤ai≤50)台洗衣机。 每个学生会从 m m m个洗衣房里随机选择一个,选择同一个洗衣房的学生会按照房间里洗衣机的数量平均排队,求最长队列人数的期望。 例如:有3个人选择了1号房间有2台洗衣机,9个人选择了2号房间有3台洗衣机,此时1号房间内最长队列长度为2,2号房间内最长队列长度为3,所以这个状态的最长队列长度为3。 传送门
这道题是一道典型的概率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]∗(l−1)+1≤p≤a[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=0l∑p=a[j]∗(l−1)+1a[j]∗lCn−j+pp∗dp[i−1][j−p][k] 2.当前的第i个房间的最长队伍小于l: 显而易见,我们的人数范围: 0 ≤ p ≤ a [ j ] ∗ ( l − 1 ) 0\leq p\leq a[j]*(l-1) 0≤p≤a[j]∗(l−1)加上组合数枚举就行了: ∑ 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]∗(l−1)Cn−j+pp∗dp[i−1][j−p][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=0∑lp=a[j]∗(l−1)+1∑a[j]∗lCn−j+pp∗dp[i−1][j−p][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=0∑a[j]∗(l−1)Cn−j+pp∗dp[i−1][j−p][l] 所以期望的题一般可以转换成概率题,概率题初始值为1然后推就完了。