poj-2151

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卡持续了半天，　后来才发现自己把　Ｔ（队伍数量　1~1000）和Ｍ（题目数量 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>，　其实只是一个概率组合.

对某些特殊情况：

ｉ< j ：　不可能，　０；

i== 0 && j == 0: 肯定会发生， 1;

ｉ>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].

最后，你可以做一个减法.