【每日一题】比赛(DP)

比赛

http://www.nowcoder.com/questionTerminal/23e79acc53ae46118f8a7d4e53b9a40b

题目梗概:

搁你面前有十二道题,你们小队有 a[i] 的概率做出来第 i 题,如果做不出来,你分别还有 b[i] 和 c[i] 的概率从你旁边那俩讨论声音贼大的队伍口中听懂怎么做 (我怀疑他们是在装逼。。(╬▔皿▔)╯),最后要你输出从 一道都不会全都会做的总共十三种情况的概率。


解题思路:

  • 很明显,因为题目之间做不做的出来没有相互影响,所以每道题做出来的概率是独立的,我们设每道题做出来的概率是 p[i] ,而做不出来的概率是 up[i],由于直接只算 p[i] 的情况较多,不便计算,所以我们先计算做不对的情况,就是 up[i]=(1-a[i])*(1-b[i])*(1-c[i])(很显然,就是三种方法都不能拯救可怜的智商的情况≡(▔﹏▔)≡)。那么,做出这道题的概率就是p[i]=1-up[i]
  • 好的,计算出了每题做出的概率之后,我们来考虑这样一种情况:紧张刺激的比赛进行到了一半,你刚刚结束了上一题,不论上一题的结果是好是坏,根据本题的设定,都对你面前的这题没有影响!那么,这道题对你比赛情况的改变是什么呢?无非就是对的题目多一道做对的题目和原来一样。因此,不论你现在做出了多少题,它们在你完成这道题的时候,概率都应该变为当前情况*这题做错的概率+做对少一题的情况*这题做对的概率:f[j]=f[j]*up[i]+f[j-1]*p[i] (i代表面对的题,j代表做对了j道题),所以我们在遇到一道新题目的时候,我们要遍历当前所有题目都做对——>一道题目都没对的情况,更新它们的概率。
  • 最后,在我们遇见完所有题目后,输出所有情况的概率即可(^∀^●)ノシ。

代码:

#include<iostream>
#include<cstdio>
using namespace std;
const int N = 15;
double a[N],b[N],c[N],p[N],up[N],f[N];
int main(){
    for(int i=0;i<3;i++)
        for(int j=1;j<=12;j++){
            if(i==0)
                cin>>a[j];
            else if(i==1)
                cin>>b[j];
            else cin>>c[j];
        } 

    for(int i=1;i<13;i++){
        up[i]=(1-a[i])*(1-b[i])*(1-c[i]);
        p[i]=1-up[i];
        //cout<<p[i]<<' '<<up[i]<<endl;
    }
    f[-1]=0; 
    f[0]=up[1];
    f[1]=p[1];
    for(int i=2;i<13;i++){
        for(int j=i;j>=0;j--){
            f[j]=f[j]*up[i]+f[j-1]*p[i];
        }
    }
    for(int i=0;i<13;i++)
        printf("%.6f\n",f[i]);

    return 0;
} 
全部评论

相关推荐

07-04 21:23
已编辑
东莞城市学院 后端
秋招和春招只收到几个中大厂的笔试,本人比较菜,感觉大厂的笔试太难,算法题不能全部做出来就没过了,但是CVTE和小天才的感觉不是很难,基本上都做出来了,笔试还是挂了。Boss上投了Java后端开发都没有回音,boss上有面试机会都是C#工控软件开发方向的,但是这个方向不太懂,资料又少,面试的表现有点差,现在还是想看看Java这边,面试的时候比较有把握点。想请教一下,这份简历还有什么问题,一直没什么机会,还有什么地方要修改的。
程序员小白条:学历太差,民办和公办,外包还得区分的,这个学历+这个简历,没的办法,除非你有人脉,太难了,这环境,何况你都毕业了,连一段实习都没,肯定没公司会挑选了,没竞争力,开发才招几个人,跟你竞争的可不是二本,三本的人哦,何况你在二本,三本里面也排名不高
投递小天才等公司7个岗位
点赞 评论 收藏
分享
自学java狠狠赚一...:骗你点star的,港卵公司,记得把star收回去
点赞 评论 收藏
分享
认真搞学习:这么良心的老板真少见
点赞 评论 收藏
分享
身边有人上海、深圳&nbsp;6、7k&nbsp;都去了,真就带薪上班了。
程序员小白条:木的办法, 以后越来越差,还是家附近宅着吧,毕业的人越来越多,岗位都提供不出来,经济又过了人口红利期
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务