题目描述
小明同学要参加一场考试，考试一共有n道题目，小明必须做对至少60%的题目才能通过考试。考试结束后，小明估算出每题做对的概率，p1,p2,…,pn。你能帮他算出他通过考试的概率吗？
输入
输入第一行一个数n（1<=n<=100），表示题目的个数。第二行n个整数，p1,p2,…,pn。表示小明有pi%的概率做对第i题。（0<=pi<=100）
输出
小明通过考试的概率，最后结果四舍五入，保留小数点后五位。
思路
二维数组DP。
对每一道题存在做对和做错两种情况，对于第i道题做对j道的概率为：
前i-1道做对j-1道且第i道做对的概率 + 前i-1道做对j道且第i道做错的概率
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| Scanner in = new Scanner(System.in);
int n = in.nextInt();
double[] p = new double[n];
for (int i = 0; i < n; i++) p[i] = (double)in.nextInt() / 100;
double[][] dp = new double[n + 1][n + 1];
dp[0][0] = 1;
for (int i = 1; i < n + 1; i++) {
dp[i][0] = dp[i - 1][0] * (1 - p[i - 1]);
for (int j = 1; j < n + 1; j++){
dp[i][j] = dp[i - 1][j - 1] * p[i - 1] + dp[i - 1][j] * (1 - p[i - 1]);
}
}
double result = 0;
for (int i = (3 * n + 4) / 5; i <= n; i++) {
result += dp[n][i];
}
System.out.println(String.format("%.5f", result));
in.close();
|
考察点