首页 > 代码库 > uva 11181

uva 11181

直接枚举计算就行;

#include<cstdio>#include<cstring>#include<algorithm>#define maxn 22using namespace std;double ans[maxn],p[maxn];bool vis[maxn];int n,r;void dfs(int cur,int cot){    if(cur>n)    {        if(cot==r)        {            double tmp=1;            for(int i=1; i<=n; i++)            {                if(vis[i])                    tmp*=p[i];                else tmp*=(1-p[i]);            }            ans[0]+=tmp;            for(int i=1; i<=n; i++)                if(vis[i])                    ans[i]+=tmp;        }        return;    }    vis[cur]=0;    dfs(cur+1,cot);    vis[cur]=1;    dfs(cur+1,cot+1);    vis[cur]=0;}int main(){    int ca=1;    while(scanf("%d%d",&n,&r)&&(n+r))    {        for(int i=0; i<=n; i++)        {            ans[i]=0;            vis[i]=0;        }        for(int i=1; i<=n; i++)            scanf("%lf",&p[i]);        dfs(1,0);        printf("Case %d:\n",ca++);        for(int i=1;i<=n;i++)            printf("%lf\n",ans[i]/ans[0]);    }    return 0;}
View Code