UVA11181 - Probability|Given（概率）

UVA11181 - Probability|Given（概率）

题目链接

题目大意：n个人去购物，要求只有k个人买东西。给你n个人每个人买东西的概率，然后要你求出这n个人中有k个人购物并且其中一个人是ni的概率pi。

解题思路：设B是n个人中选择k个人。设Ai是除了第i个人外选择k - 1个人。那么P = P（Ai）? pi / P(B);所以用dfs求出B，和Ai的概率，然后代入公式得到最后的结果。

代码：

#include <cstdio>
#include <cstring>

const int maxn = 25;

int N, K;
int vis[maxn];
double p[maxn];

double dfs (int k, int cnt, int b) {

    if (k == cnt) {

        double tmp = 1.0;
        for (int i = 0; i < N; i++)
            if (!vis[i])
                tmp *= (1.0 - p[i]);
        return tmp;
    }

    double ans = 0;
    for (int i = b; i < N; i++) {
        if (!vis[i]) {
            vis[i] = 1;
            ans += dfs(k + 1, cnt, i + 1) * p[i]; 
            vis[i] = 0;
        }
    }
    return ans;
}

int main () {

    int cas = 0;
    while (scanf ("%d%d", &N, &K) && (N || K)) {

        for (int i = 0; i < N; i++)
            scanf ("%lf", &p[i]);

        printf ("Case %d:\n", ++cas);
        double pb = dfs(0, K, 0);
        double pa;
        for (int i = 0; i < N; i++) {
            vis[i] = 1;
            pa = dfs (0, K - 1, 0) * p[i];    
            printf ("%.6lf\n", pa/pb);
            vis[i] = 0;
        }
    }
    return 0;
}

UVA11181 - Probability|Given（概率）

原文：http://blog.csdn.net/u012997373/article/details/41120197