cf261 B. Maxim and Restaurant（01背包+排列组合）

题意：

n个客人，每个客人有体积 \(a_i\)。客人随机排列成一排，依次进入容积为p的餐厅，直到某个客人进不了了就停止（就算后面有个体积超小的也没法进）。求能进去的客人数的期望。

\(1\le n,p,a_i \le 50\)

思路：

先特判一下所有人都能进。

\(f(i,j,k)\) 表示在前 \(i\) 个人中选 \(j\) 个（不计顺序），总体积为 \(k\) 的方案数。

\(f(i,j,k)+=f(i-1,j-1, k-a_i)\) ，可以优化掉一维变成 \(f(j,k)\)，记得倒序更新。

设进来了 \(j\) 个人后，第 \(i+1\) 个人恰好进不来，则有 \(k\le p,a_{i+1}> p-k \implies k \in [\max\{0,p-a_{i+1}+1\},p]\)

枚举第 \(i+1\) 个人，

注意这里 \(f(j,k)\) 表示在n个人中选 \(j\) 个，但不能选 \(a_{i+1}\)，总体积恰为 \(k\) 的方案数。为此，每次都重新求dp

const int N = 53;
int n, a[N], p;
db jie[N], f[N][N], ans;

signed main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    cin >> p;

    if(accumulate(a + 1, a + 1 + n, 0) <= p)
        return cout << n, 0; //特判

    jie[0] = 1; //预处理阶乘
    for(int i = 1; i <= n; i++) jie[i] = i * jie[i-1];

    for(int x = 1; x <= n; x++) //枚举进不来的那个人
    {
        //dp,01背包求方案数
        memset(f, 0, sizeof f);
        f[0][0] = 1;
        for(int i = 1; i <= n; i++) if(i != x) //忽略a[x]
            for(int j = i; j >= 1; j--)
                for(int k = p; k >= a[i]; k--)
                    f[j][k] += f[j-1][k-a[i]];

        //统计答案
        for(int j = 1; j <= n; j++) //进来的人数
            for(int k = max(0, p-a[x]+1); k <= p; k++) //进来的人要填充的体积
                ans += j * jie[j] * jie[n-j-1] * f[j][k];
    }

    cout << ans / jie[n];
}