OR54. 礼物
描述
“呼！！佳慧，我拿到面试直通卡了！”“吓死宝宝了！哦，你拿到直通卡了啊，好哒，进去吧，你可以直接接受老大的面试了”。 亮亮来到老大的办公室，“骚年，你想做什么工作啊？”“我要做大数据分析！！” “哦~~那你先帮我们解决一个问题。是这样的，我们这次招聘会一共有N个人，我们公司给大家准备了一些礼物，但是我们并不知道这些人具体喜欢什么，现在库房共有m种礼物，每种礼物有Ci件，共N件。而我们大致知道每个人选择某种礼物的概率，即能知道Pij(编号为i的人选择第j种礼物的概率)。现在所有人按编号依次领礼物（第1个人先领，第N个人最后领），领礼物时，参加者会按照预先统计的概率告诉准备者自己想要哪一种礼物，如果该种礼物在他之前已经发放完了则他会领不到礼物，请帮我们计算出能能领到礼物的期望人数。
输入描述
第一行包含两个整数N(1≤N≤300),M(1≤M≤100)，用单个空格隔开。表示公有N个应聘者，M种礼物。 第二行为M个整数，依次为Ci，第i种礼物的个数。 接下来的N行，每行M个实数，一次为Pij，第i个人选择第j种礼物的概率。输出描述
一行输出期望人数。结果保留1位小数。示例1
输入:
2 2 1 1 0.3 0.7 0.7 0.3
输出:
1.6(样例解释：共有4种选择(1,1),(1,2),(2,1),(2,2)，概率分别为0.21、0.09、0.49、0.21，(1,1),(2,2)这两种选择只有1个人能拿到礼物，(1,2),(2,1)这两种选择有2个人能拿到礼物，所以期望为1*(0.21+0.21) + 2*(0.09+0.49) = 1.58，保留一位小数为1.6。)
C++ 解法, 执行用时: 5ms, 内存消耗: 484KB, 提交时间: 2020-10-31
#include <bits/stdc++.h>
using namespace std;
#define MP make_pair
#define X first
#define Y second
#define forl(i, s, e) for (int i = s; i < e; i++)
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, M;
int total= 0;
while (cin >> N >> M) {
int gift[M];
forl(i, 0, M) {
cin >> gift[i];
total += gift[i];
}
vector<double> prob[303];
forl(i, 0, N) {
prob[i] = vector<double> (M);
forl(j, 0, M)
cin >> prob[i][j];
}
double left_all = 0.;
forl(i, 0, M) {
if (gift[i] == 0)
continue;
vector<double> left = vector<double>(gift[i]+1, 0);
left[gift[i]] = 1;
forl(j, 0, N) {
left[0] = left[1] * prob[j][i] + left[0];
forl(k, 1, gift[i]) {
left[k] = left[k] * (1 - prob[j][i]) +
left[k+1] * prob[j][i];
}
left[gift[i]] = left[gift[i]] * (1-prob[j][i]);
}
double exp_left = 0.;
forl(k, 0, gift[i]+1)
exp_left += k * left[k];
left_all += exp_left;
}
cout << fixed << setprecision(1) << N - left_all << '\n';
}
return 0;
}
C++ 解法, 执行用时: 5ms, 内存消耗: 504KB, 提交时间: 2020-10-31
#include <bits/stdc++.h>
using namespace std;
#define MP make_pair
#define X first
#define Y second
#define forl(i, s, e) for (int i = s; i < e; i++)
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, M;
int total= 0;
while (cin >> N >> M) {
int gift[M];
forl(i, 0, M) {
cin >> gift[i];
total += gift[i];
}
vector<double> prob[303];
forl(i, 0, N) {
prob[i] = vector<double> (M);
forl(j, 0, M)
cin >> prob[i][j];
}
double left_all = 0.;
forl(i, 0, M) {
if (gift[i] == 0)
continue;
vector<double> left = vector<double>(gift[i]+1, 0);
left[gift[i]] = 1;
forl(j, 0, N) {
left[0] = left[1] * prob[j][i] + left[0];
forl(k, 1, gift[i]) {
left[k] = left[k] * (1 - prob[j][i]) +
left[k+1] * prob[j][i];
}
left[gift[i]] = left[gift[i]] * (1-prob[j][i]);
}
double exp_left = 0.;
forl(k, 0, gift[i]+1)
exp_left += k * left[k];
left_all += exp_left;
}
cout << fixed << setprecision(1) << N - left_all << '\n';
}
return 0;
}