11181-Probability

不得不说这道题十分猥琐啊，递归求解，我RE了接近20次，最后发现还是数组开小了。

#include<stdio.h>
#include<iostream>
#include<math.h>
#include<vector>
#include<string.h>
using namespace std;
int biao[250000],n,r,zhi = 0;
double p[250000],possi[250000];
int v[250000][25];
void dfs(int cur,int buy)
{
    if(cur == n)
    {
        if(buy != r) return;
        possi[zhi] = 1;
        for(int i = 0;i < n;i++)
        {
            if(biao[i]) v[zhi][i] = 1;
            else v[zhi][i] = 0;
        }
        for(int i = 0;i < n;i++)
        {
            if(biao[i])
                possi[zhi] *= p[i];
            else possi[zhi] *= (1 - p[i]);
        }
        zhi++;
        return;
    }
    biao[cur] = 1; //买
    dfs(cur + 1,buy + 1);
    biao[cur] = 0;  //不买
    dfs(cur + 1,buy);
}
int main()
{
//    freopen("out.txt","w",stdout);
    int kase = 0;
    while(cin>>n>>r)
    {
        if(!n && !r) break;
        printf("Case %d:\n",++kase);
        memset(v,0,sizeof(v));
        memset(p,0,sizeof(p));
        memset(possi,1,sizeof(possi));
        memset(biao,0,sizeof(biao));
        for(int i = 0;i < n;i++)
            cin>>p[i];
        dfs(0,0);
        double fenmu = 0;
        for(int i = 0;i < zhi;i++)
            fenmu += possi[i];
        for(int i = 1;i <= n;i++)  //看看哪个容器里有i,把i买了的概率求出来
        {
            double fenzi = 0;
            for(int j = 0;j < zhi;j++)
            {
                double temp = 1;int flag =0;
                if(v[j][i - 1])  //这种情况i买了
                {
                    flag = 1;
                    for(int k = 0;k < n;k++)
                    {
                        if(v[j][k]) temp *= p[k];
                        else temp *= (1 - p[k]);
                    }
                }
                if(flag) fenzi += temp;
            }
            printf("%.6lf\n",(double)fenzi*1.0/fenmu);
        }
    }
    return 0;
}

11181-Probability,布布扣,bubuko.com

11181-Probability

原文：http://blog.csdn.net/glqglqglq2/article/details/38586767