NC219633. ResearchProductivityIndex
描述
if one paper is submitted and it gets accepted, the index is ;
if 4 papers are submitted and all get accepted, the index is ;
if 10 papers are submitted and 3 get accepted, the index is ;
if 5 papers are submitted and 4 get accepted, the index is ;
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); }