POJ-2151 Check the difficulty of problems 概率DP-白红宇

POJ-2151 Check the difficulty of problems 概率DP

阅读量：4649 次

发布时间：2019-06-09

本文共 1115 字，大约阅读时间需要 3 分钟。

　　题目链接：

　　组合数做肯定超时，容易看出是DP。f[i][j]表示某个队的前j个题目做出i个题目的概率，则f[i][j]=f[i][j-1]*(1-num[j])+f[i-1][j-1]*num[j]。接下来就直接好求了，对每个队求出至少答对一个的概率，然后依次相乘就是满足题目的第一个条件，然后再减去每个队答对n-1个的概率的积就是最终概率了。

1 //STATUS:C++_AC_32MS_192KB 2 #include
     
       3 #include
      
        4 #include
       
         5 #include
        
          6 #include
         
           7 #include
          
            8 #include
           
             9 #include
            
             10 #include
             
              11 #include
              
               12 #include
               13 using namespace std;14 #define LL __int6415 #define pii pair
                
                 16 #define Max(a,b) ((a)>(b)?(a):(b))17 #define Min(a,b) ((a)<(b)?(a):(b))18 #define mem(a,b) memset(a,b,sizeof(a))19 #define lson l,mid,rt<<120 #define rson mid+1,r,rt<<1|121 const int N=1010,INF=0x3f3f3f3f,MOD=1999997;22 const LL LLNF=0x3f3f3f3f3f3f3f3fLL;23 24 double num[35],win[2],f[35][35];25 int m,t,n;26 27 void dp()28 {29 int i,j;30 win[0]=win[1]=0;31 f[0][0]=1;32 for(j=1;j<=m;j++)33 f[0][j]=f[0][j-1]*(1-num[j]);34 for(j=1;j<=m;j++){35 for(i=1;i<=j;i++)36 f[i][j]=f[i][j-1]*(1-num[j])+f[i-1][j-1]*num[j];37 }38 for(i=1;i

转载于:https://www.cnblogs.com/zhsl/archive/2013/01/06/2846975.html

你可能感兴趣的文章