【每日一题】比赛（DP）

题目梗概：

搁你面前有十二道题，你们小队有 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;
}