POJ2151Check the difficulty of problems

时间：2024-01-05 12:57:38

题意 ： 举办一次比赛不容易，为了不让题目太难，举办方往往希望能够讲出的题目满足两点，1是所有的队伍都至少能够解出一个题目，2是冠军队至少能解出确定数量的题目，最后让你求的是每个队伍至少解出一道题并且冠军队伍解出N道题的概率.

思路 ： 我觉得吧，搞ACM不容易，唉，概率这玩意儿，一不小心漏掉一个就完啦。。。。首先呢，概率得好好求，其次呢DP得会一些。。。。

这个题的思路我觉得小优姐的CSDN已经说得很详细了http://blog.csdn.net/lyy289065406/article/details/6648579

样例解释 ： 2 2 2

0.9 0.9

1 0.9

第一行M,T,N代表着M道题，T个队伍，希望冠军队做出N道题。接下来是T行M列，表示（i，j）点表示队伍 i 做对 j题的概率是多少。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<cmath>

using namespace std ;

const int maxn =  ;

const int maxm =  ;

double f[maxm][maxn];

double dp[maxm][maxn][maxn];

int main()

{

     int M,T,N ;//题目数，队伍数，冠军队做出题目数

     while(~scanf("%d %d %d",&M,&T,&N))

     {

         if(M == &&N == && T == )

         break ;

         memset(dp,,sizeof(dp));

         for(int i =  ; i <= T ; i++)

         {

             for(int j =  ; j <= M ; j++)

             scanf("%lf",&f[i][j]);

         }

         for(int i =  ; i <= T ; i++)

         {

             dp[i][][] = 1.0 ;

             for(int j =  ; j <= M ; j++)

             {

                 dp[i][j][] = dp[i][j-][]*(-f[i][j]);

                 for(int k =  ; k <= j ; k++)

                 {

                     dp[i][j][k] = dp[i][j-][k-]*f[i][j]+dp[i][j-][k]*(-f[i][j]);

                 }

             }

         }

         double p1 = 1.0 ;

         for(int i =  ; i <= T ; i++)

          p1 *= ( - dp[i][M][]) ;

         double p2 = 1.0 ;

         for(int i =  ; i <= T ; i++)

         {

             double sum =  ;

             for(int j =  ; j < N ; j++)

             sum += dp[i][M][j];

             p2 *= sum ;

         }

         printf("%.3f\n",p1-p2);

     }

     return ;

}

相关文章