牛客——比赛（DP DFS 二进制枚举）

题意：

给定每个题可以解出（独立和偷听）的概率，求解出0~12题的概率。

思路：

首先可以算出每个题解出的概率，即1-解不出该题的概率，即

///计算独立的每道题解出来的概率
    for(int i=1;i<=12;i++){
        double tmp=(1-a[i])*(1-b[i])*(1-c[i]);
        ac[i]=1-tmp;
    }

再考虑如何计算解出0~12题的概率。因为数据范围很友好，可以用dfs或状压枚举或dp。

思路一：DP

考虑用dp[i] [j]表示只做前i个题做对了j个题的概率。那么很容易可以推出分界点就是第i个题是否做对。

如果第i个题做不对，那么dp[i] [j]就可以由dp[i-1] [j]转移而来。

如果第i个题做的对，那么dp[i] [j]就可以由dp[i-1] [j-1]转移而来。

即

 dp[i][j]=dp[i-1][j]*(1-ac[i])+dp[i-1][j-1]*ac[i];

要注意初始化dp[0] [0] =1,表示前0个题做对0个题的概率是1

以及转移过程中对j==0的特殊处理。

完整代码如下：

#include<bits/stdc++.h>
using namespace std;
const int maxn=15;
double a[maxn],b[maxn],c[maxn];
double dp[maxn][maxn];
double ac[maxn];///一道题解出来的概率

int main(){
    for(int i=1;i<=12;i++) cin>>a[i];
    for(int i=1;i<=12;i++) cin>>b[i];
    for(int i=1;i<=12;i++) cin>>c[i];

    ///dp[i][j]表示只做前i个题做对了j个题的概率

    ///计算独立的每道题解出来的概率
    for(int i=1;i<=12;i++){
        double tmp=(1-a[i])*(1-b[i])*(1-c[i]);
        ac[i]=1-tmp;
    }

    dp[0][0]=1;
    for(int i=1;i<=12;i++){
        dp[i][0]=dp[i-1][0]*(1-ac[i]);
        for(int j=1;j<=i;j++){
            dp[i][j]=dp[i-1][j]*(1-ac[i])+dp[i-1][j-1]*ac[i];
        }
    }
    for(int i=0;i<=12;i++){
        printf("%.6f\n",dp[12][i]);
    }

    return 0;
}

思路二：状压枚举

用二进制数表示每道题是否解出的状态，在每一种状态下枚举每一道题是否被解出，计算相应的概率即可。

#include<bits/stdc++.h>
using namespace std;
const int maxn=15;
double a[maxn],b[maxn],c[maxn];
double dp[maxn];
double ac[maxn];///一道题解出来的概率

int main(){
    for(int i=0;i<12;i++) cin>>a[i];
    for(int i=0;i<12;i++) cin>>b[i];
    for(int i=0;i<12;i++) cin>>c[i];

    ///计算独立的每道题解出来的概率
    for(int i=0;i<12;i++){
        double tmp=(1-a[i])*(1-b[i])*(1-c[i]);
        ac[i]=1-tmp;
    }

   for(int i=0;i<(1<<12);i++){
       int tmp=0;
       double tt=1;
       for(int j=0;j<12;j++)
           if((1<<j)&i){
               tmp++;
               tt*=ac[j];
           }
           else tt*=(1-ac[j]);
       dp[tmp]+=tt;
   }
    for(int i=0;i<=12;i++)
        printf("%.6f\n",dp[i]);

    return 0;
}

思路三：DFS

跟状压枚举的思路基本一致，只是换了种实现形式。具体可参考：传送门