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]); } }