当前位置: 首页 > 图灵资讯 > 技术篇> poj-2151

poj-2151

来源:图灵教育
时间:2023-05-24 09:27:06

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

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

上一篇:

poj-3349

下一篇:

poj-1080