admin 管理员组

文章数量: 1184232

楚楚街2016校招 ——礼物（动态规划）

题目描述

“呼！！佳慧，我拿到面试直通卡了！”“吓死宝宝了！哦，你拿到直通卡了啊，好哒，进去吧，你可以直接接受老大的面试了”。
亮亮来到老大的办公室，“骚年，你想做什么工作啊？”“我要做大数据分析！！”
“哦~~那你先帮我们解决一个问题。是这样的，我们这次招聘会一共有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位小数。

输入例子:

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。)

#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
int main() {int n, m, i, j, k;double left_gift;vector<int> gift_count;    //礼物的数量vector<vector<double> > ps;//每个人选每种礼物的概率vector<double> left_n_p;   //对每一种礼物最后剩余的数量为x的概率while(cin >> n >> m){gift_count.assign(m, 0);ps.assign(n, vector<double>(m, 0));left_gift = 0;for (i = 0; i < m; ++i)  cin >> gift_count[i]; for (i = 0; i < n; ++i)for (j = 0; j < m; ++j)cin >> ps[i][j];for (i = 0; i < m; ++i) { //循环计算每一种礼物left_n_p.assign(gift_count[i] + 2, 0);left_n_p[gift_count[i]] = 1;for (j = 0; j < n; ++j) { //每一个人领取礼物后更新 left_n_p[0] = left_n_p[0] + left_n_p[1] * ps[j][i];for (k = 1; k <= gift_count[i]; ++k)left_n_p[k] = left_n_p[k] * (1 - ps[j][i]) + left_n_p[k + 1] * ps[j][i];}for (j = 1; j <= gift_count[i]; ++j)left_gift += left_n_p[j] * j;}printf("%.1f\n", n - left_gift);}return 0;
}

本文标签： 楚楚街2016校招 礼物（动态规划）

版权声明：本文标题：楚楚街2016校招 ——礼物（动态规划） 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://www.roclinux.cn/b/1693757602a241063.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。