比赛 题解

一开始以为求第0-12个问题的解决概率懵逼了很久

一道简单的概率dp/dfs问题

我们先求出每个问题的解决概率。

我们运用正难则反的思想，先求出我们不能解决第i个问题的概率，即：

然后，用1减去这个概率就是第i个题可以解决的概率了，设为

那么，现在就可以随便乱搞了。

注意到，n很小，可以直接dfs搞，每个点成功和失败都枚举一次，复杂度

还有更优秀的就是用概率dp来解决。

我们设表示前i个问题中，对了j个问题的概率。初始化

那么，直接类似0/1背包转移即可（需要注意的是，到这里不能直接转移,还要乘上失败概率）

那么就有转移方程:

【因为这个情况第i个问题不可能成功，所以单独讨论】

【分第i个问题成功和失败两个情况考虑即可】

最后输出即可,复杂度

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=13;
double a[N],b[N],c[N],d[N];
double dp[N][N];
int main(){
    for(int i=1;i<=12;++i){
        scanf("%lf",&a[i]);
    }
    for(int i=1;i<=12;++i){
        scanf("%lf",&b[i]);
    }
    for(int i=1;i<=12;++i){
        scanf("%lf",&c[i]);
    }
    for(int i=0;i<=12;++i){
        d[i]=(1-a[i])*(1-b[i])*(1-c[i]);
        d[i]=1-d[i];
    }
    dp[0][0]=1;
    for(int i=1;i<=12;++i){
        dp[i][0]=dp[i-1][0]*(1-d[i]);
        for(int j=1;j<=i;++j){
            dp[i][j]=dp[i-1][j]*(1-d[i])+dp[i-1][j-1]*d[i];
        }
    }
    for(int i=0;i<=12;++i){
        printf("%.6lf\n",dp[12][i]);
    }
    return 0;
}