题解 | #招聘会小礼品#

解题思路

这是一道概率期望计算题目。给定 $N$ 个人和 $M$ 个物品，每个物品有一个容量上限 $C[i]$ ，每个人对每个物品都有一个选择概率 $P[i][j]$ 。需要计算最终未被选中的人数的期望。

解题步骤：

对每个物品分别计算其被选中 $k$ 个人的概率（ $k$ 从 $0$ 到 $C[i]$ ）
使用动态规划的思想，逐个人更新概率分布
计算每个物品的期望选中人数，累加得到总的期望选中人数
用总人数 $N$ 减去期望选中人数即为答案

代码

c++
java
python

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    
    // 初始化容量数组和概率矩阵
    vector<int> C(M);
    vector<vector<float>> P(N, vector<float>(M));
    
    // 输入每个物品的容量
    for(int i = 0; i < M; i++) {
        cin >> C[i];
    }
    
    // 输入每个人选择每个物品的概率
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> P[i][j];
        }
    }
    
    vector<float> p_sel(N + 1);
    float E_sel = 0;
    
    // 对每个物品分别计算
    for(int i = 0; i < M; i++) {
        fill(p_sel.begin(), p_sel.end(), 0.0);
        p_sel[C[i]] = 1.0;
        
        // 对每个人进行概率更新
        for(int j = 0; j < N; j++) {
            for(int k = 0; k <= C[i]; k++) {
                if(k == 0)
                    p_sel[k] = p_sel[k] + p_sel[k+1] * P[j][i];
                else if(k < C[i])
                    p_sel[k] = p_sel[k] * (1-P[j][i]) + p_sel[k+1] * P[j][i];
                else
                    p_sel[k] = p_sel[k] * (1-P[j][i]);
            }
        }
        
        // 计算期望值
        for(int k = 0; k <= C[i]; k++) {
            E_sel += k * p_sel[k];
        }
    }
    
    printf("%.1f", N-E_sel);
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        
        // 初始化容量数组和概率矩阵
        int[] C = new int[M];
        float[][] P = new float[N][M];
        
        // 输入每个物品的容量
        for(int i = 0; i < M; i++) {
            C[i] = sc.nextInt();
        }
        
        // 输入每个人选择每个物品的概率
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                P[i][j] = sc.nextFloat();
            }
        }
        
        float[] p_sel = new float[N + 1];
        float E_sel = 0;
        
        // 对每个物品分别计算
        for(int i = 0; i < M; i++) {
            Arrays.fill(p_sel, 0.0f);
            p_sel[C[i]] = 1.0f;
            
            // 对每个人进行概率更新
            for(int j = 0; j < N; j++) {
                for(int k = 0; k <= C[i]; k++) {
                    if(k == 0)
                        p_sel[k] = p_sel[k] + p_sel[k+1] * P[j][i];
                    else if(k < C[i])
                        p_sel[k] = p_sel[k] * (1-P[j][i]) + p_sel[k+1] * P[j][i];
                    else
                        p_sel[k] = p_sel[k] * (1-P[j][i]);
                }
            }
            
            // 计算期望值
            for(int k = 0; k <= C[i]; k++) {
                E_sel += k * p_sel[k];
            }
        }
        
        System.out.printf("%.1f", N-E_sel);
    }
}

N, M = map(int, input().split())

# 初始化容量数组和概率矩阵
C = list(map(int, input().split()))
P = []
for _ in range(N):
    P.append(list(map(float, input().split())))

E_sel = 0

# 对每个物品分别计算
for i in range(M):
    p_sel = [0.0] * (N + 1)
    p_sel[C[i]] = 1.0
    
    # 对每个人进行概率更新
    for j in range(N):
        for k in range(C[i] + 1):
            if k == 0:
                p_sel[k] = p_sel[k] + p_sel[k+1] * P[j][i]
            elif k < C[i]:
                p_sel[k] = p_sel[k] * (1-P[j][i]) + p_sel[k+1] * P[j][i]
            else:
                p_sel[k] = p_sel[k] * (1-P[j][i])
    
    # 计算期望值
    for k in range(C[i] + 1):
        E_sel += k * p_sel[k]

print(f"{N-E_sel:.1f}")

算法及复杂度

算法：动态规划 + 概率计算。通过动态规划更新每个状态的概率分布，最后计算期望值。
时间复杂度： $\mathcal{O}(MN\cdot \max(C))$ ，其中 $M$ 是物品数， $N$ 是人数， $C$ 是最大容量。
空间复杂度： $\mathcal{O}(N\cdot M)$ ，主要用于存储概率矩阵。

关键点解释

p_sel[k] 表示选中 $k$ 个人的概率分布
对每个人的概率更新分为三种情况：
- $k=0$ ：只能从 $k+1$ 转移过来
- $0<k<C[i]$ ：可以保持不变或从 $k+1$ 转移
- $k=C[i]$ ：只能保持不变
最终的期望值通过概率分布与对应人数的乘积求和得到