2017-04-16 编程题-通过考试

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

解法：可以用暴力求解，但是肯定会超时。优化程度不好的DFS只有40%，不过好像有优化地比较好的能到100%。当然最理想的做法是用DP做，这里是二维DP。

用f(i,j)表示小明在前i道题目中能答出j道题目的概率。状态转移公式为

f(i,j) = f(i-1,j-1) * pi + f(i-1,j) * (1-pi) 这是当j > 0时

最后将f(n, i) 中i达标的值相加即为答案。

public static void main(String[] args) {
	
	Scanner scanner = new Scanner(System.in);
	
	int n = scanner.nextInt();
	double[] p = new double[n];
	
	for (int i = 0; i < n; i++)
		p[i] = (double) scanner.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 = 0; i < n + 1; i++) {
		if ( 5 * i >= 3 * n )
			result += dp[n][i];
	}
	
	
	
} 

Written on April 16, 2017