XidianOJ 1020 ACMer去刷题吧

题目描述

刷题是每个ACMer必由之路，已知某oj上有n个题目，第i个题目小X能做对的概率为Pi(0<=Pi<=1，1<=i<=n) 求小X至少做对k道题的概率

输入

第一行输入一个正整数t，(t<=20)，表示有t组测试样例。第二行输入正整数n，k，（1<=n,k<=1000）第三行输入n个小数，分别为Pi(1<=i<=n,0<=Pi<=1)，表示小X做对第i个题目的概率。

输出

输出小X至少做对k道题的概率，并换行（保留4位小数）

--正文

f[i][j] 为在做了i道的时候，做对j道的概率

f[i][j] = f[i-1][j-1] * p[i] ＋f[i-1][j] * (1- p[i])

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

double pr[];

double f[][];

int main(){

    int time,T;

    scanf("%d",&T);

    for (time=;time<=T;time++){

        int n,k;

        scanf("%d %d",&n,&k);

        int i,j;

        for (i=;i<=n;i++){

            scanf("%lf",&pr[i]);

        }

        memset(f,,sizeof(f));

        f[][] = ;

        for (i=;i<=n;i++){

            f[i][] = f[i-][] * ( - pr[i]);

            for (j=;j<=i;j++){

                f[i][j] = f[i-][j-]*pr[i] + f[i-][j] * ( - pr[i]);

            }

        }

        double sum = ;

        for (i=k;i<=n;i++){

            sum += f[n][i];

        }

        printf("%.4lf\n",sum);

    }

    return ;

}