比赛 (dfs)

题意：

题目链接：https://ac.nowcoder.com/acm/problem/14734

你在打比赛，这场比赛总共有12个题

对于第i个题，你的队伍有a[i]的几率解决她

如果解决不了她呢？

由于所有人讨论的都很大声

所以你有b[i]的概率从左边那个队那里听会这个题的做法

有c[i]的概率从右边那个队那里听会这个题的做法

请问最终你们队伍解出0-12题的概率分别是多少

输入描述:

第一行12个数表示a[1] -> a[12]
第二行12个数表示b[1] -> b[12]
第三行12个数表示c[1] -> c[12]

输出描述:

输出13行，第i行表示解出i-1题的概率
保留6位小数

题解：对于一道题其正确率为d[i]=1-(1-a[i])(1-b[i])(1-c[i]);(高中基本概率问题）
然后每一题均有两种状态：正确或错误。一共12道题，dfs暴力一下即可。

#include <bits/stdc++.h>
using namespace std;
double a[20],b[20],c[20],d[20];
double ans[20];
void dfs(int x,int num,double res){
    //x:上一个题号 num:正确题数 res：概率
    if(x>=12){
        ans[num]+=res;
        return;
    }
    dfs(x+1,num,res*(1-d[x+1])); //该题（x+1题）错误
    dfs(x+1,num+1,res*d[x+1]);    //该题（x+1题）正确
}
int main() {
    int n=12;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1;i<=n;i++) cin>>c[i];
    for(int i=1;i<=n;i++) d[i]=1-(1-a[i])*(1-b[i])*(1-c[i]);
    dfs(0,0,1.0);
    for(int i=0;i<=n;i++) printf("%.6f\n",ans[i]);

    return 0;
}