比赛

https://ac.nowcoder.com/acm/problem/14734

题目理解：题意很简单，就是给你12道题3种途径的概率，求解决0~12题的概率。

题目分析：正着求每道题解决的概率，显然有点困难，那么我们不妨逆向考虑一下每道题无法解决的概率，答案显然 fail[i]=(1-a[i])(1-b[i])(1-c[i]) ** (fail[i]表示第i题无法解决的概率)，之后就可以得知每道题成功的概率ac[i]=1-wa[i]。注意一下数据，总题数才12道，直接暴力dfs就行了，复杂度O(n^2)，稳过，放弃思考dp了。

代码：

#include<stdio.h>
int n=12,i,j;
double a[16],b[16],c[16],wa[16],ac[16],ans[16];
void dfs(int now,int acc,double pro){//now表示当前解题位置，acc表示题目解决数量，pro代表当前情况概率
    if(now==13){
        ans[acc]+=pro;//加上当前概率
        return;
    }
    dfs(now+1,acc+1,pro*ac[now]);//当前成功
    dfs(now+1,acc,pro*wa[now]);//当前失败
}
int main()
{
    for(i=1;i<=n;i++){
        scanf("%lf",&a[i]);
    }
    for(i=1;i<=n;i++){
        scanf("%lf",&b[i]);
    }
    for(i=1;i<=n;i++){
        scanf("%lf",&c[i]);
    }
    for(i=1;i<=n;i++){
        wa[i]=(1-a[i])*(1-b[i])*(1-c[i]);//第i题没解出的概率
        ac[i]=1-wa[i];//第i题成功解出的概率
    }
    dfs(1,0,1.0);
    for(i=0;i<=n;i++){
        printf("%.6lf\n",ans[i]);
    }
}