G++ 1188K 79MS.
#include <stdio.h> #include <string.h> double DP[50][50]; double P[1010]; double PSolveN[1010][50]; double PSolveNAcc[1010][50]; void getMENP(double * array, int N, int length, int M, double (* PSolveN)[50] ) // MENP: more/equal N questions probability { // printf("N %d length %d M %d\n", N, length, M); // if (N > length) { // return 0; // } memset(DP, 0, sizeof(DP)); int i = 0; for (; i <= length; i++) { int j = 0; for (; j<=M; j++) { if (i < j) { // imposible DP[i][j] = 0; } else if (i == 0 && j == 0) { // must be DP[i][j] = 1; } else if (j == 0) { DP[i][j] = (1-array[i-1]) * DP[i-1][j]; } else { double p1 = DP[i-1][j]; double p2 = DP[i-1][j-1]; double solveThisP = p2*array[i-1]; double noSolveThisP = p1*(1- array[i-1]); DP[i][j] = solveThisP + noSolveThisP; // printf("%d %d %lf\n", i, j, DP[i][j]); } } } for (int j = 0; j <=length; j++) { (*PSolveN)[j] = DP[length][j]; } } int main() { int M; int T; int N; while(1){ memset(P, 0, sizeof(P)); memset(PSolveN, 0, sizeof(PSolveN)); memset(PSolveNAcc, 0, sizeof(PSolveNAcc)); double res = 0; double AllME1P = 1; double AllllNME1 = 1; scanf("%d %d %d", &T, &M, &N); if (0 == M && 0 == T && 0 == N) { return 0; } if (T < N) { printf("%.3f\n", 0.0); continue; } int i = 0; for (; i < M; i++) { int j = 0; for (; j < T; j++) { scanf("%lf", P+j); } getMENP(P, N, T, M, PSolveN + i); } for (i = 0; i< M; i++) { int j = 0; for (; j <= T; j++) { if (0 == j) { PSolveNAcc[i][j] = PSolveN[i][j]; } else { PSolveNAcc[i][j] = PSolveN[i][j] + PSolveNAcc[i][j-1]; } // printf("%d %d %.3lf ", i ,j, PSolveNAcc[i][j]); } // printf("\n"); } for (i = 0; i < M; i++) { AllME1P *= (1-PSolveN[i][0]); } for (i = 0; i < M; i++) { AllllNME1 *= (PSolveNAcc[i][N-1] - PSolveNAcc[i][0]); } res = AllME1P - AllllNME1; // printf("%f %f\n", AllME1P, AllLNME1); printf("%.3f\n", res); } }
悲催一题, 因为RE卡持续了半天, 后来才发现自己把 T(队伍数量 1~1000)和M(题目数量 1~ 30) 搞混了, 这将不可避免地导致数组访问中的错误,
当时发现了这个问题,输入的时候颠倒了,但是用过的数组尺寸没有交换。妈的,真的超出了我的想象。 后来,为了检查RE,poj被直接用作调试器...
悲剧的是,最后直接看代码发现的问题... 唉, 发现自己现在的思维有问题,写完code后,懒得再仔细检查,直接上数据,错了再用数据debug,
诚然, 很多算法题第一次写对还是挺难的,但是不能因为这个而完全指望测试。毕竟测试有自己的覆盖范围。(poj 很多AC最后还是有问题的)。
以后一定要加强对code的审查,就像现在的工作一样,不能指望别人code rebview给你发现了问题。一个合格的程序员必须对自己的code有最清晰和肯定的理解.
唉,其实我现在有时候是codee。 AC了, 还是没有底,一定要消除这个问题。.
回到问题本身, 我在刷题指南里看到这个问题,被分到hash,其实应该不是, 硬归,就是概率论+DP.
DP在这里的作用是找出来 一支队伍在整场比赛中解决k道题的概率, 一开始,我想按照传统的数学思维,后来发现我死了。看了discuss后,我想DP确实可以在这里使用:
以前解DP题大多是为了最优解,每个解之间都要比较,但这只是DP的一种类型,有些DP, 它不需要最优解,而是子问题解之间的组合。
对于某一队(解题概率数组P), 定义D[i][j]在前i题中解决j道题的概率, 然后,有:
D[i][j] = D[i-1][j]*(1- P[i])<第一个问题没有解决,前i-1个问题已经解决了j道 > + D[i-1][j-1]*P[i]<解决第一道题, 前i-1的问题解决了j-1>, 其实只是一个概率组合.
对某些特殊情况:
i< j : 不可能, 0;
i== 0 && j == 0: 肯定会发生, 1;
i>0 & j == 0, D[i][j] = D[i-1][j]*(1- P[i]) D[i-1][j-1] 没有意义的情况(问题是-1), 从概率论上看,第一道解决0道题的概率必须等于(1-P[i]) *<解决前i-1题,解决0道的概率>, 因为不可能解决负数问题.
取出这个数组后 i= M的情况,这意味着 在比赛中,球队解决了第一名 0, 1 ,2 ,3 ... M题的概率 ,事实上,一个二维数组认为每个团队都有自己的数组.
然后,根据题意, 只有每个队解决了>=1道题, 至少由一队解决了>=N题(注意,这里至少有一队, 这意味着许多团队解决了同样数量的问题>=N题也是合理的解决方案).
啊,此时显示了概率论的不足, 想了很久,我找不到一种简单的概率组合方法来表达合理的理解.
后来想出来,满足解的概率应该是这样的:
每一队都解决了>=1道题的概率 - 每一队都解决了>=一个问题,但每对只解决了<N道题.
用之前解决的前i问题解决j问题概率数组PSolven,进行处理:
使用PSolveNAccc[i][j] 表示对于第一队,在比赛中 至少解决了j道题的概率(并解决了0, 1 ,2 ..j 问题概率的总和),
然后PSolveNAccc[i][j] = PSolveN[i][j] + PSolveNAcc[i][j-1].
最后,你可以做一个减法.
![](/images/780-200-2.jpg)