京东实习编程题-小明考试通过概率

好吧，有答案了，确实DP。。。服气。我自己是完全没想到用DP优化。。 概率dp，定义状态前i个题目对j个的概率，递推求解 示例代码： #include <bits/stdc++.h> #define maxn 109 using namespace std; int n,a[maxn]; double dp[maxn][maxn]; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); dp[0][0]=1; for(int i=1;i<=n;i++){ dp[i][0]=dp[i-1][0]*(100.0-a[i])/100; for(int j=1;j<=i;j++) dp[i][j]=dp[i-1][j]*(100.0-a[i])/100+dp[i-1][j-1]*1.0*a[i]/100; } int low=(3*n+4)/5; double ans=0; for(int i=low;i<=n;i++) ans+=dp[n][i]; printf("%.5f\n",ans); //system("pause"); return 0; }

动态规划，我的是AC

跪了。。。

你理解错了，要 所有正确的题目的正确率相乘+所有错误的题目的(1-正确率)相乘

public class Main { static double[][] m; public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNextInt()) { int num = sc.nextInt(); m = new double[num + 1][num + 1]; for (int i = 0; i < num + 1; i++) m[i] = new double[num + 1]; int[] p = new int[num]; for (int i = 0; i < num; i++) p[i] = sc.nextInt(); System.out.println(ans(p)); } } private static String ans(int[] p) { m[1][0] = (100 - p[0]) / 100.0; m[1][1] = p[0] / 100.0; for (int i = 2; i <= p.length; i++) { double fail = (100 - p[i - 1]) / 100.0; double suc = p[i - 1] / 100.0; m[i][0] = m[i - 1][0] * fail; for (int j = 1; j <= i; j++) { m[i][j] = m[i - 1][j] * fail + m[i - 1][j - 1] * suc; } } double res = 0; int suc = (int) Math.ceil(p.length * 0.6); for (int i = suc; i <= p.length; i++) res += m[p.length][i]; DecimalFormat df = new DecimalFormat("0.00000"); return df.format(res); } }

可是每题概率不同。。你咋n选k   列子是正好每题都是50

塞马网论坛有答案