Research Productivity Index概率dp

题目链接

#include <bits/stdc++.h>
 
using namespace std;
 
int n;
double tot,now;
double a[105];
double dp[102][102]; // 交前i个，j个ac.
 
int main()
{
    cin >> n;
    for ( int i=1; i<=n; i++ ) {
        int x;
        scanf("%d",&x);
        a[i] = x*0.01;
    }
    sort(a+1,a+n+1,greater<double>());
    dp[0][0] = 1;
    double ans = 0;
    for ( int i=1; i<=n; i++ ) {
        dp[i][0] = dp[i-1][0]*(1-a[i]);
        for ( int j=1; j<=i; j++ ) {
            dp[i][j] = dp[i-1][j]*(1-a[i]) + dp[i-1][j-1]*a[i];
        }
        double now = 0;
        for ( int j=1; j<=i; j++ ) {
            now += dp[i][j]*pow(j,1.0*j/i);
        }
        ans = max(ans,now);
    }
    printf("%.9f
",ans);
 
    return 0;
}