OR90. 招聘会小礼品
描述
输入描述
第一行包含两个整数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++ 解法, 执行用时: 4ms, 内存消耗: 376KB, 提交时间: 2020-10-31
#include<stdio.h>
#include<stdlib.h>
#include<memory.h>
int main()
{
int N,M;
scanf("%d%d",&N,&M);
int C[M];
float P[N][M];
memset(C,0,sizeof(int)*M);
memset(P,0,sizeof(float)*N*M);
for(int i=0;i<M;i++)
{
scanf("%d",&C[i]);
}
for(int i=0;i<N;i++)
{
for(int j=0;j<M;j++)
{
scanf("%f",&P[i][j]);
}
}
float p_sel[N+1];
float E_sel = 0;
for(int i=0;i<M;i++)
{
memset(p_sel,0.0,sizeof(float)*(N+1));
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 = E_sel + k*p_sel[k];
}
}
printf("%.1f",N-E_sel);
return 0;
}
C 解法, 执行用时: 4ms, 内存消耗: 376KB, 提交时间: 2019-05-26
#include<stdio.h>
#include<stdlib.h>
#include<memory.h>
int main()
{
int N,M;
scanf("%d%d",&N,&M);
int C[M];
float P[N][M];
memset(C,0,sizeof(int)*M);
memset(P,0,sizeof(float)*N*M);
for(int i=0;i<M;i++)
{
scanf("%d",&C[i]);
}
for(int i=0;i<N;i++)
{
for(int j=0;j<M;j++)
{
scanf("%f",&P[i][j]);
}
}
float p_sel[N+1];
float E_sel = 0;
for(int i=0;i<M;i++)
{
memset(p_sel,0.0,sizeof(float)*(N+1));
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 = E_sel + k*p_sel[k];
}
}
printf("%.1f",N-E_sel);
return 0;
}