UVa 11181 Probability|Given：DFS及贝叶斯公式

UVa 11181 Probability|Given：DFS及贝叶斯公式2014-07-07 synapse7 11181 - Probability|Given

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=115&page=show_problem&problem=2122

思路：

拿样例一的“三选二”为例：

分母怎么求？P=买*买*不买+买*不买*买+不买*买*买=0.092，这是三个人中恰有两个人买东西的概率。

分子怎么求？P（1号买了）=买*买*不买+买*不买*买=0.038，所以在有2个人买了东西的情况下1号买了东西的概率是0.038/0.092≈0.413403

但这样有重复计算，所以我们不妨在枚举组合（计算分母）时顺带把对应的分子也算出来，详见代码。

完整代码：

01./*0.076s*/02.03.#include<cstdio>04.#include<cstring>05.const int N = 25;06.07.int n;08.double p[N], ans[N];09.10.double dfs（int cnt, int r, double pi）11.{12.if （cnt == n） return r ？ 0.0 : pi;///r没选完就是0，选完就返回pi13.double sum = 0.0;14.if （r）15.{16.sum += dfs（cnt + 1, r - 1, pi * p[cnt]）;///选这个人17.ans[cnt] += sum;///分子18.}19.sum += dfs（cnt + 1, r, pi * （1 - p[cnt]））;///不选这个人20.return sum;21.}22.23.int main（）24.{25.int cas = 0, r, i;26.double P;27.while （scanf（"%d%d", &n, &r）, n）28.{29.for （i = 0; i < n; ++i） scanf（"%lf", &p[i]）;30.memset（ans, 0, sizeof（ans））;31.printf（"Case %d:
", ++cas）;32.P = dfs（0, r, 1.0）;///分母33.for （i = 0; i < n; ++i）34.printf（"%.6f
", ans[i] / P）;35.}36.return 0;37.}