CF261B Maxim and Restaurant
daitouzero
·
·
题解
什么人能一个人比一张能坐 50 个人的桌子宽？
题意
有个餐馆，有容积 p ，有 n 个人，每个人体积是 a_{i}
这 n 个人进入的次序完全是随机的，求餐馆里面吃饭人数的期望
p,n,a_{i}\le50
Solve
进入次序就是排列，所以答案最后除个 n!
容易发现一旦餐馆塞满了后面人甭管怎么排都进不去
而一个人能不能排进去也和餐馆里面都塞了些什么人才无关，只用考虑餐馆的容量
考虑枚举进不去餐馆的最后一个人，设 dp[i][j][k] 为前 i 个人进去 j 个人占据 k 个空间的方案数
枚举第一个进不去的人，每次重新把 DP 做一遍（就是不让这个人参与 DP 方程的更新），那么答案总的式子就是
ans=\frac{\sum_{x=1}^{n}\sum_{i=1}^{n-1}\sum_{j=p-a_{x}}^{p}dp[n][i][j]\times j\times i!\times(n-(i+1))!}{n!}
这么做的话总复杂度就是 O(n^3p)，但是因为 n,p 很小，所以足以通过此题
但我们还有 O(n^2p) 的做法，先看式子：
ans=\frac{\sum_{i=1}^{n}\sum_{j=0}^{p}dp[i][j]\times i!\times (n-i)!}{n!}
这个式子着实有点迷惑，它计算的实际上是在餐馆里的人，有第一个人，有第二个人到有第 ？ 个人中，每个人出现的次数
也就是它每次算的是有多少种情况里面会有第几个人
把式子调整一下表达，可能会更好理解
\sum_{i=1}^{n}(\sum_{j=0}^{p}dp[i][j])\times 1\times i!\times (n-i)!
$1$ 代表有正在计算的这一 ‘位子’ 上的人的队列长度，一个人自然长度为 $1
dp[i][j] 表示里面有 i 个人，占有 j 个空间的方案数
可能会觉得很奇怪，感觉这玩意会算重，但并不会，因为你每次统计的贡献不是整个在餐馆里面的人的贡献，而是这个餐馆里面第 i 号人会出现几次
\sum_{j=0}^{p}dp[i][j]$ 表示的就是一共会有几种方案餐馆里面会出现不少于 $i$ 个人，每个人都不一样，所以得乘个 $i!\times (n-i)!
Code
```cpp
#include<cstdio>
#include<iostream>
#include<cstring>
typedef long long ll;
typedef long double ldouble;
typedef unsigned long long ull;
const int N=55;
ll n,a[N],p,dp[N][N];
double fact[N],sum;
int main()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);std::cout.tie(0);
std::cin>>n;
fact[0]=1;
for (int i=1;i<=n;i++)
{
std::cin>>a[i];
fact[i]=fact[i-1]*i,
sum+=a[i];
}
std::cin>>p;
if (sum<=p)
{
std::cout<<(double)n;
return 0;
}
dp[0][0]=1;
for (int i=1;i<=n;i++)
for (int j=i;j>=1;j--)
for (int k=p;k>=a[i];k--)
dp[j][k]+=dp[j-1][k-a[i]];
double ans=0;
for (int i=1;i<=n;i++)
for (int j=0;j<=p;j++)
ans+=dp[i][j]*fact[i]*fact[n-i];
std::cout<<ans/fact[n];
return 0;
}
```