问题描述

• 汽车载重限制：贝茜的汽车最大载重为 p。
• 奶牛信息：约翰家有 n 头奶牛，每头奶牛的重量为 a[i]。
• 上车规则：
• 奶牛们按随机顺序排队上车。
• 当一头奶牛准备上车时，如果将其加入车内后，总重量超过 p，贝茜会停止接载这头奶牛及其后面的所有奶牛。
• 即使后面的奶牛更轻，也不会被接载。

目标：计算贝茜能够接待的奶牛数量的数学期望。

数学期望

数学期望（期望值）是概率论中衡量随机变量平均值的重要概念。在本问题中，我们的随机变量是贝茜能够接载的奶牛数量。数学期望可以帮助我们了解在所有可能的随机排列下，贝茜平均能够接载多少头奶牛。

线性期望原理

数学期望的一个重要性质是线性期望，即：

$$ E(X + Y) = E(X) + E(Y) $$

这意味着即使两个随机变量 X 和 Y 相关，期望值仍然是各自期望值的和。在本问题中，我们可以利用线性期望将复杂问题分解为更简单的部分。

具体来说，我们可以将总接载奶牛数 X 分解为每头奶牛是否被接载的指示变量之和：

$$ X = X_1 + X_2 + \dots + X_n $$

其中：

$$ X_i = \begin{cases} 1 & \text{如果第 } i \text{ 头奶牛被接载} \\ 0 & \text{否则} \end{cases} $$

根据线性期望：

$$ E(X) = E(X_1) + E(X_2) + \dots + E(X_n) $$

因此，我们只需要分别计算每头奶牛被接载的概率 E(X_i)，然后将这些概率相加，就能得到总的数学期望。

解决思路

为了计算每头奶牛被接载的概率 E(X_i)，我们需要分析在随机排列下，第 i 头奶牛被接载的条件。

1. 随机排列下的位置分析

考虑第 i 头奶牛在随机排列中的位置。由于排列是完全随机的，每头奶牛在任何位置出现的概率是均等的，即每个位置的概率为 1/n。

设第 i 头奶牛在第 k 个位置（k 从 1 到 n），则：

• 前面有 k-1 头奶牛已经上车。
• 第 i 头奶牛是否能上车，取决于前面 k-1 头奶牛的总重量加上她自己的重量是否超过载重限制 p。

具体条件为：

$$ W + a[i] \leq p $$

其中，W 是前面 k-1 头奶牛的总重量。

2. 计算前 k-1 头奶牛的总重量限制

由于奶牛的排列是随机的，前 k-1 头奶牛是从剩下的 n-1 头奶牛中随机选择的。因此，我们需要计算从 n-1 头奶牛中随机选择 k-1 头，其总重量不超过 p - a[i] 的概率。

3. 动态规划（DP）解决子集和问题

为了计算从 n-1 头奶牛中选取 k-1 头，且总重量不超过 p - a[i] 的子集数量，我们可以使用动态规划（DP）的方法。

DP 状态定义

定义 dp[size][sum] 表示从 n-1 头奶牛中选取 size 头，使得它们的总重量恰好为 sum 的子集数量。

• 状态：
• size: 选取的奶牛数量。

• sum: 选取的奶牛总重量。

• 初始状态：

• dp[0][0] = 1：选取 0 头奶牛，总重量为 0 的子集只有一种，即不选任何奶牛。

• 其他状态初始为 0。

• 状态转移：

• 对于每头奶牛的重量 w，更新 dp：

  $$ dp[size][sum] += dp[size - 1][sum - w] $$

  这表示，通过选取 size - 1 头奶牛，总重量为 sum - w 的子集，再加上当前这头重量为 w 的奶牛，就可以得到 size 头奶牛，总重量为 sum 的子集。

实现步骤

1. 初始化 DP 数组：

dp[0][0] = 1;

1. 遍历每头奶牛，更新 DP 数组：

对于每头奶牛的重量 w，从后向前遍历 size 和 sum，避免重复计算。

for(auto w : b){
   for(int size = n-2; size >=0; size--){
       for(int sum = p; sum >= w; sum--){
           dp[size+1][sum] += dp[size][sum - w];
       }
   }
}

这里，b 是不包含第 i 头奶牛的其他 n-1 头奶牛的重量数组。

4. 计算每头奶牛的被接载概率

对于每头奶牛 i，她被接载的概率 E(X_i) 可以通过以下步骤计算：

1. 遍历所有可能的位置 k（从 1 到 n）：

2. 第 i 头奶牛在第 k 个位置的概率为 1/n。

3. 前 k-1 头奶牛的总重量需要满足 W ≤ p - a[i]。

4. 计算满足条件的子集数量：

5. 通过之前的 DP 数组 dp[k-1][sum]，累加所有 sum ≤ p - a[i] 的子集数量。

6. 计算当前位置的概率贡献：

7. 满足条件的子集数量除以总的可能子集数量 C(n-1, k-1)，得到在第 k 个位置上，前 k-1 头奶牛总重量不超过限制的概率。

8. 乘以该位置出现的概率 1/n，得到第 k 个位置对 E(X_i) 的贡献。

9. 累加所有位置的贡献，得到 E(X_i)。

5. 汇总所有奶牛的期望值

通过对所有奶牛的被接载概率 E(X_i) 求和，可以得到总的期望值 E(X)：

$$ E(X) = \sum_{i=1}^{n} E(X_i) $$

实现细节

1. 组合数的预计算

在计算概率时，我们需要用到组合数 $\binom{n}{k}$，表示从 n 个元素中选取 k 个的方式数。为了提高效率，我们可以提前计算所有可能的组合数，并存储在二维数组中。

2. 动态规划优化

由于奶牛的数量和重量都较小（n ≤ 50，a[i] ≤ 50），我们使用二维数组来存储 DP 状态。

3. 代码实现

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; // 奶牛数量
    cin >> n;
    vector<int> a(n); // 奶牛重量数组
    for(int &x : a) cin >> x;
    int p; // 汽车最大载重
    cin >> p;

    // 预先计算组合数 C(n,k) 并存储在 comb 数组中
    // comb[i][j] 表示从 i 个元素中选取 j 个的组合数 C(i,j)
    vector<vector<long long>> comb(n+1, vector<long long>(n+1, 0));
    comb[0][0] = 1;
    for(int i=1; i<=n; i++){
        comb[i][0] = 1; // C(i,0) = 1
        for(int j=1; j<=i; j++){
            comb[i][j] = comb[i-1][j-1] + comb[i-1][j];
        }
    }

    double ans = 0.0; // 最终的期望值

    // 遍历每一头奶牛，计算其被接载的概率
    for(int i=0; i<n; i++){
        // 构建不包含第i头奶牛的奶牛数组 b
        vector<int> b;
        b.reserve(n-1);
        for(int j=0; j<n; j++) {
            if(j != i) b.push_back(a[j]);
        }

        // 使用动态规划计算子集数量
        // dp[size][sum] 表示选取 size 头奶牛，总重量为 sum 的子集数量
        // 初始化 dp 数组
        vector<vector<long long>> dp(n, vector<long long>(p+1, 0));
        dp[0][0] = 1; // 选取0头奶牛，总重量为0的子集只有1种

        // 遍历每头奶牛的重量，更新 dp
        for(auto w : b){
            // 从后向前遍历，避免重复计算
            for(int size = n-2; size >=0; size--){
                for(int sum = p; sum >= w; sum--){
                    dp[size+1][sum] += dp[size][sum - w];
                }
            }
        }

        double p_i = 0.0; // 第i头奶牛被接载的概率

        // 遍历所有可能的位置 k
        for(int k=1; k<=n; k++){
            // 当第i头奶牛在第k个位置时，前面有k-1头奶牛
            int sz = k-1;
            if(sz > n-1) continue; // 不可能的情况

            // 计算满足条件的子集数量：选取 sz 头奶牛，总重量 ≤ p - a[i]
            int limit = p - a[i];
            if(limit < 0){
                // 当前奶牛的重量已经超过载重限制，无法被接载
                continue;
            }

            long long valid_subsets = 0;
            // 累加所有总重量 ≤ limit 的子集数量
            for(int sum = 0; sum <= min(p, limit); sum++) {
                valid_subsets += dp[sz][sum];
            }

            // 计算当前 k 的概率贡献
            double ways = (double)valid_subsets;
            double total = (sz >=0 && sz <=n-1) ? comb[n-1][sz] : 0.0; // C(n-1, sz)

            if(total > 0){
                // 位置为 k 的概率为 1/n
                // 前面子集满足条件的概率为 ways / total
                p_i += (1.0 / n) * (ways / total);
            }
        }

        // 累加到总期望值
        ans += p_i;
    }

    // 输出结果，保留足够的精度
    cout << fixed << setprecision(10) << ans << "\n";

    return 0;
}

解释

输入读取：

• 首先读取奶牛的数量 n。
• 接着读取每头奶牛的重量 a[i]。
• 最后读取汽车的最大载重 p。

组合数预计算：

• 使用二维数组 comb 预先计算所有的组合数 $\binom{n}{k}$，以便后续快速查找。
• 组合数的递推公式为：

$$ \binom{i}{j} = \binom{i-1}{j-1} + \binom{i-1}{j} $$

并且 $\binom{i}{0} = 1$。

遍历每头奶牛：

• 对于每头奶牛 i，我们需要计算她被接载的概率 p_i。
• 为此，首先构建一个不包含第 i 头奶牛的数组 b。

动态规划计算子集数量：

• 初始化 dp[size][sum] 数组，其中 size 表示选取的奶牛数量，sum 表示选取的奶牛总重量。
• 初始状态为 dp[0][0] = 1。
• 遍历数组 b 中的每头奶牛的重量 w，并更新 dp 数组。
• 更新方式为从后向前遍历 size 和 sum，避免重复计算。

计算每个位置的概率贡献：

• 对于每个可能的位置 k（从 1 到 n），计算第 i 头奶牛在该位置被接载的概率。
• 如果当前奶牛的重量 a[i] 已经超过载重限制 p，则无法被接载，跳过该位置。
• 否则，累加所有满足总重量 ≤ p - a[i] 的子集数量。
• 计算当前位置的概率贡献，并累加到 p_i 中。

汇总期望值：

• 将每头奶牛的接载概率 p_i 累加到总的期望值 ans 中。

输出结果：

• 最后，输出总的期望值 ans，并确保输出的精度满足题目对误差的要求。

复杂度分析

时间复杂度

总体时间复杂度为 O(n^2 * p)。

总体时间复杂度为 O(n^3 * p)。

空间复杂度

总体空间复杂度为 O(n^2 + n * p)。