Research Productivity Index-概率dp

题目描述

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 nn 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.

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 nn 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 (1≤n≤100), the number of Angela’s candidate papers. The next line has nn space-separated integers giving the probability of each paper getting accepted. Each probability value is given as an integer percentage between 11 and 100100, 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 10-6

示例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

题意是：

给出n份论文，每一分论文都有被接受以及被打回的可能性，输入有n个数，表示每一份被接受可能性的百分比，数据在1-100之间

可以想到，我们用数组记录概率，然后再状态转移的过程中记录最大

dp[i][j]代表前[i]个论文中，通过[j]篇论文的概率，贪心的考虑一下的话，我们要将接受概率大的放到前面，接受概率小的放到后面，这样能够保证一定的正确性，当然是先提交被接受概率大的呀

然后一定是j <= i的

在转移的过程中，dp[i][j] == dp[i-1][j] * P当前论文不通过 + dp[i-1][j-1] * P当前论文通过 （一开始没有考虑不通过的那部分，直接gg）在处理的时候要注意一下边界问题，在这个问题中有一个dp[0][0]要初始化为1.0，这样在传递的过程中可以保证正确性（1.0 × 任何数不影响结果）

然后除了角落dp[0][0]之外，还有dp[i][0]没有处理，每一个dp[i][0]都可以通过前面的dp[i-1][0]转移过去，转移的方程就是：

dp[i][0] == dp[i-1][0] * P当前论文不通过

注意输入的是1–100,在处理的过程中要将这个数 × 0.01 or / 100来进行处理

int n;
double a[107];
double dp[107][107];
bool cmp(double a, double b)
{
    return a > b;
}
int main()
{
    cin >> n;
    double ans = 0;
    for(int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + 1 + n, cmp);
    dp[0][0] = 1.0;
    for(int i = 1; i <= n; i++)
    {
        dp[i][0] = dp[i - 1][0] * (100 - a[i]) * 0.01;
    }
    for(int i = 1; i <= n; i++)
    {
        double sum = 0;
        for(int j = 1; j <= i; j++)
        {
            dp[i][j] = dp[i - 1][j] * (100 - a[i]) * 0.01 + dp[i - 1][j - 1] * a[i] * 0.01;
            sum += dp[i][j] * pow(j, 1.0 * j / (1.0 * i));
        }
        ans = max(ans, sum);
    }
    printf("%.10lf\n", ans);
    return 0;
}

文章知识点与官方知识档案匹配，可进一步学习相关知识

算法技能树leetcode-动态规划22-括号生成7775 人正在系统学习中