概率DP Research Productivity Index 一维DP的优化 邮票收集问题的拓展

题目链接:https://ac.nowcoder.com/acm/contest/13168/G
这篇博客重点在一维优化代码的初始化操作.
题目要求:给n份论文,每份有k的可能性通过,有一种独特的方法来评估论文提交的成功。他们使用‎‎的研究生产力指数‎‎，定义为a^(a/s)‎其中‎s‎是提交的文件总数,a‎是会议接受的文件数量.
例如‎:如果提交一个文件并被接受，索引是‎1^(1/1)=1;
‎如果提交了‎‎10‎‎篇论文，并接受了‎‎3‎‎篇论文，索引3^(3/10)≈1.390389.
有N个论文 如果明智地选择提交哪些论文，她的研究生产力指数的最大预期值是什么.

一个比较常规的概率DP,比赛时题目没搞清楚,思路有点偏,就放弃了,去做别的题目.

二维
dp[i][j]=dp[i-1][j](1-a[i]/100.0)+dp[i-1][j-1]a[i]/100.0;
dp[i][j]表示第i件物品中过了j件物品的概率.如果第i件过了,那么就是dp[i-1][j-1]a[i]的概率,如果第i件没过就是dp[i-1][j](1-a[i])的概率.

二维DP
double dp[105][105];
int a[105];
bool cmp(int x,int y)
{
    return x>y;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    sort(a+1,a+1+n,cmp);
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        dp[i][0]=dp[i-1][0]*(1-a[i]/100.0);
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            dp[i][j]=dp[i-1][j]*(1-a[i]/100.0)+dp[i-1][j-1]*a[i]/100.0;
    double ans=0;
    double tem=0;
    for(int i=1;i<=n;i++)
    {
        tem=0;
        for(int j=1;j<=i;j++)
        {
            tem+=dp[i][j] * pow(j, j * 1.0 / i);

        }
        ans=max(ans,tem);
    }
    printf("%.9lf\n",ans);
}

一维DP
一维思路
由于dp[i][j]=dp[i-1][j](1-a[i]/100.0)+dp[i-1][j-1]a[i]/100.0;
dp[i][j]是由dp[i][j-1]推导而来所以是逆序.

double dp[105];
double a[105];
bool cmp(double x,double y)
{
    return x>y;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        a[i]=a[i]/100.0;
    }
    sort(a+1,a+1+n,cmp);
    dp[0]=1;
    double ans=0;
    for(int i=1;i<=n;i++)//提交数量
    {
        double tem=0;

        for(int j=i;j>=1;j--)//通过数量.
        {
            dp[j]= dp[j-1]*a[i] + dp[j]*(1-a[i]);
            tem+=dp[j]*pow(j,j*1.0/i);
        }
        dp[0]=dp[0]*(1-a[i]);
        ans=max(ans,tem);
    }
    printf("%.9lf\n",ans);
}