题意：

举办一次ACM竞赛，需要考虑两方面，1.是每个队至少都能做出1道题目，2.是冠军至少能做出n道题目。现在已知有m道题目，t支队伍，和n的值，以及每支队伍做出每道题目的概率gl[i][j]，求出这次比赛能保证上面两方面都会达到的概率。

PS：我代码中的n和m是反的。

 

思路：

这个题应该算是基础的概率dp了，就是一个加法原理和乘法原理，其他和普通dp一样，甚至方程更简单

dp[i][j][k]表示第i个队伍，做前j道题目，作对k道的概率，方程很好写吧~

我们可以把最终的答案转化成 每个队伍都做至少一道题目的概率-每个队伍都只做1~(n-1)道题的概率

好了，就是这样了~

 

1 #include 
      
        2 #include 
       
         3 #include 
        
          4  5 #define N 40 6 #define M 1010 7  8 using namespace std; 9 10 double gl[M][N],dp[M][N][N];11 int n,m,t;12 13 void go()14 {15     for(int i=1;i<=t;i++)16         for(int j=1;j<=n;j++)17             scanf("%lf",&gl[i][j]);18     memset(dp,0,sizeof dp);19     for(int i=1;i<=t;i++)20     {21         dp[i][0][0]=1.0;22         for(int j=1;j<=n;j++)23         {24             dp[i][j][0]=dp[i][j-1][0]*(1.0-gl[i][j]);25             for(int k=1;k<=j;k++)26                 dp[i][j][k]=dp[i][j-1][k-1]*gl[i][j]+dp[i][j-1][k]*(1.0-gl[i][j]);27         }28     }29     double ans1=1.0,ans2=1.0;30     for(int i=1;i<=t;i++) ans1*=(1.0-dp[i][n][0]);31     for(int i=1;i<=t;i++)32     {33         double tmp=0.0;34         for(int j=1;j