招聘会小礼品

	# Algorithm:
# the problem of calcu the number of prizes obtained is equal to the problem of calcu the number
# of prizes left behind, that is, getPrize = N - leftPrize.
# So, we can easily calcu the prob (p_k) of the prize j (j: 1~M) left with k (k: 1~C[j]) items  
# after the selecting process of i (i: 1~N) interviewees in each iteration, 
# that is, p_k' = p_k*(1-P[i][j]) + p_(k+1)*P[i][j]
def prizeGetFunc(N,M,C,P):
    """"
    Parameters
    ----------
    N :   number of interviewees
    M :   kinds of the gifts
    C :   number of each gift
    P :   preferential matrix
    """
    leftPrize = 0     # initiate the number of prizes left
    for j in range(M):
        prizeLeftPro = [0]*C[j]+[1]  # initialize the left prob of each prize (from 0 to C[j])
        for i in range(N):
            prizeLeftPro[0] += prizeLeftPro[1] * P[i][j] # left 0, prizes of kind i are all given
            for k in range(C[j]):
                prizeLeftPro[k] = prizeLeftPro[k]*(1-P[i][j]) + prizeLeftPro[k+1]*P[i][j] # update the p_k
            prizeLeftPro[C[j]] = prizeLeftPro[C[j]]*(1-P[i][j])
        for k in range(1,C[j]+1):
            leftPrize += prizeLeftPro[k]*k # calculate the expected number of prizes left
    getPrize = round(N-leftPrize,1) 
    return getPrize



	N = int(raw_input())
    M = int(raw_input())
    C = map(int,raw_input().split())
    P = [[map(int,raw_input().split())] for i in range(N)]
    getPrize = prizeGetFunc(N,M,C,P)
    print getPrize        

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

int main()
{
    int M, N;
    cin >> N >> M;
    // N✖️M 矩阵
    vector<vector<float>> P(N, vector<float>(M));
    vector<int> gifts(M);
    for (int i = 0; i < M; i++)
    {
        cin >> gifts[i];
    }

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> P[i][j];
        }
    }
    // dp 是M✖️N的矩阵, dp[i][j]表示第i种物品被前不被前j个人选中的概率
    vector<float> obj_pos(M);
    // 对每个物品单独处理
    for (int i = 0; i < M; i++)
    {
        auto *dp = new vector<float>(gifts[i] + 1, 0.0);
        (*dp)[0] = 1 - P[0][i];
        (*dp)[1] = P[0][i];
        for (int j = 1; j < N; j++)
        {
            for (int k = min(gifts[i],j); k >= 1; k--)
            {
                if (k == gifts[i])
                {

                    (*dp)[k] = (*dp)[k] + (*dp)[k - 1] * P[j][i];
                }
                else
                {
                    (*dp)[k] = (*dp)[k] * (1 - P[j][i]) + (*dp)[k - 1] * P[j][i];
                }
            }
            (*dp)[0] = (*dp)[0] * (1 - P[j][i]);
        }
        
        for (int k = 0; k <= gifts[i]; k++)
        {
            obj_pos[i] += k * (*dp)[k];
        }
        delete dp;
    }
    float sum = 0;
    for (auto e : obj_pos)
    {
        sum += e;
    }
    cout << fixed << setprecision(1) << sum << endl;
}

//问了kimi给的方法，没有通过。
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt(); // 应聘者的数量
        int M = scanner.nextInt(); // 小礼品的种类数

        int[] C = new int[M]; // 小礼品的数量
        double[][] P = new double[N][M]; // 选择小礼品的概率矩阵

        // 读取每种小礼品的数量
        for (int i = 0; i < M; i++) {
            C[i] = scanner.nextInt();
        }

        // 读取每个人选择每种小礼品的概率
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                P[i][j] = scanner.nextDouble();
            }
        }

        double expectedCount = calculateExpectedGifts(N, M, C, P);
        System.out.printf("%.1f\n", expectedCount); // 输出期望人数，保留一位小数
    }

    private static double calculateExpectedGifts(int N, int M, int[] C, double[][] P) {
        double expectedCount = 0;
        double[] giftsLeft=new double[M];// 当前剩余的小礼品数量
        for (int i = 0; i < M; i++) {
            giftsLeft[i] = C[i]; // 将整数数组C转换为double数组
        }
        for (int i = 0; i < N; i++) {
            double[] giftsLeftNext = Arrays.copyOf(giftsLeft, M);
            for (int j = 0; j < M; j++) {
                // 更新每种小礼品剩余的数量
                giftsLeftNext[j] -= P[i][j] * giftsLeft[j];
            }
            giftsLeft = giftsLeftNext;

            // 计算当前人能领到小礼品的期望数量
            for (int j = 0; j < M; j++) {
                expectedCount += Math.max(0, 1 - giftsLeft[j] / (C[j] + 1e-5));
            }
        }

        return expectedCount;
    }
}

import itertools
# 能实现，但是耗费时间太多，先占个坑等想出来了再补充吧- -
nm = input().split()
n, m = int(nm[0]), int(nm[1])
gifts_types = list(range(m))
gifts_num = list(map(int, input().split()))
prob_gifts = []
total_exp = 0
for _ in range(n):
    prob_gifts.append(list(map(float, input().split())))
for choice in itertools.product(gifts_types, repeat=n):
    temp_dict = {}
    prob_temp = 1
    for j in range(n):
        if choice[j] not in temp_dict.keys():
            temp_dict[choice[j]] = choice.count(choice[j])
        prob_temp *= prob_gifts[j][choice[j]]
    if prob_temp > 0:
        num_temp = 0
        for k in temp_dict.keys():
            num_temp += min(temp_dict[k], gifts_num[k])
    else:
        continue
    total_exp += prob_temp * num_temp
print("%.1f" % total_exp)