京东笔试---通过考试（DP）

题目描述

小明同学要参加一场考试，考试一共有n道题目，小明必须作对至少60%的题目才能通过考试。考试结束后，小明估算出每题作对的概率，p1,p2,...,pn,你能帮他算出他通过考试的概率吗？

输入

输入第一行一个数n（1<=n<=100）,表示题目的个数，第二行n个整数，p1,p2,...,pn，表示小明有pi%的概率作对第i题。（0<=pi<=100）

输出

小明通过考试的概率，最后结果四舍五入，保留小数点后五位。

样例输入

50 50 50 50

样例输出

0.31250

Hint

第一个样例中，每道题做对的概率都是0.5，想要通过考试至少要作对三题。所以最后的答案就是(C4(3)+C4(4))*0.5^4=5/16;

代码如下：

#include<iostream>

#include<algorithm>

#include<stdio.h>

#include<string.h>

#include<math.h>

using namespace std;

double dp[][];

double s[];

double p[];

int main()

{

    int n;

    scanf("%d",&n);

    int num=n*0.6;

    if(num<n*0.6) num++;

    for(int j=; j<=n; j++)

        scanf("%lf",&p[j]),p[j]=p[j]/;

    dp[][]=;

    for(int j=; j<=n; j++)

    dp[j][]=dp[j-][]*(-p[j]);

    for(int j=; j<=n; j++)

    for(int k=; k<=j; k++)

        dp[j][k]=dp[j-][k-]*p[j]+dp[j-][k]*(-p[j]);

    s[]=dp[n][];

    for(int k=; k<=n; k++)

    s[k]=s[k-]+dp[n][k];

    printf("%.5lf\n",-s[num-]);

    return ;

}

巴特西

京东笔试---通过考试（DP）

最新文章

热门文章