列表

详情


NC219633. ResearchProductivityIndex

描述

Angela is a new PhD student and she is nervous about the upcoming paper submission deadline of this year's research conference. She has been working on multiple projects throughout the past year. Luckily most of the projects concluded successfully, and she came up with  candidate papers. However not all of the papers were born equal——some have better results than others. Her advisor believes she should only submit the papers with "good enough" results so they have a high chance of getting accepted.

Angela's research group has a unique way of evaluating the success of paper submissions. They use the research productivity index, defined as , where  is the total number of papers submitted, and  is the number of papers that are accepted by the conference. When , the index is defined to be zero. For example:


Intuitively, to get a high research productivity index one wants to get as many papers accepted as possible while keeping the acceptance rate high.

For each of her  papers, Angela knows exactly how likely it is that the conference would accept the paper. If she chooses wisely which papers to submit, what is the maximum expected value of her research productivity index?

输入描述

The first line of the input has a single integer , the number of Angela's candidate papers. The next line has  space-separated integers giving the probability of each paper getting accepted. Each probability value is given as an integer percentage between  and , inclusive.

输出描述

Output the maximum expected value of Angela's research productivity index. Your answer is considered correct if it has an absolute or relative error of no more than .

示例1

输入:

5
30 50 70 60 90

输出:

2.220889579

示例2

输入:

6
30 90 30 90 30 90

输出:

2.599738456

示例3

输入:

4
10 10 10 10

输出:

0.368937005

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C++(clang++11) 解法, 执行用时: 15ms, 内存消耗: 408K, 提交时间: 2021-03-23 10:45:01

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e2+10;
double dp[maxn],p[maxn];
int main()
{
	int n;scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int t1;scanf("%d",&t1);p[i]=t1/100.0;
	}
	sort(p+1,p+1+n);double ans=0;dp[0]=1;
	for(int i=n;i>=1;i--){
		dp[n+1]=0;
		for(int j=n;j>=0;j--){
			dp[j+1]+=dp[j]*p[i];
			dp[j]=dp[j]*(1-p[i]);
		}double temp=0;
		for(int j=1;j<=n;j++){
			temp+=dp[j]*pow(j,1.0*j/(n-i+1));
		}ans=max(ans,temp);
	}
	printf("%.10lf\n",ans);
}

上一题