UVa 11181 Probability|Given (条件概率 & 深度优先搜索)

发表于 更新于 分类于

题目

题目大意

有\(n\)个人准备去超市逛, 其中第\(i\)个人买东西的概率是\(P_i\)。逛完以后你得知有\(r\)个人买了东西。根据这一信息, 请计算出每个人实际买了东西的概率。输入\(n\)(\(1 ≤ n ≤ 20\))和 \(r\)(\(0 ≤ r ≤ n\)), 输出每个人实际买了东西的概率。

题解

用DFS枚举每一种可能的情况, sum[n]表示总概率, sum[i]表示第\(i\)个人买了东西的概率之和, 则答案为sum[i]/sum[n]。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <cstdio>
#include <cstring>
#include <algorithm>
int n, r;
double probabilities[30], sum[30];
bool vis[30];
int cases;
inline void DepthFirstSearch(const int&, const int&, const double&);
int main(int argc, char const *argv[]) {
  while (~scanf("%d %d", &n, &r) && (n || r)) {
    for (register int i(0); i < n; ++i) {
      scanf("%lf", &probabilities[i]);
    }
    std::fill(sum, sum + 30, 0.0);
    memset(vis, 0, sizeof(vis));
    DepthFirstSearch(0, 0, 1);
    printf("Case %d:\n", ++cases);
    for (register int i(0); i < n; ++i) {
      printf("%.6lf\n", sum[i] / sum[n]);
    }
  }
}
inline void DepthFirstSearch(const int &cur, const int &countt, const double &probability) {
  if(countt > r || cur - countt > n - r) return;
  if(cur == n) {
    sum[n] += probability;
    for (register int i(0); i < n; ++i) {
      if (vis[i]) {
        sum[i] += probability;
      }
    }
    return;
  }
  vis[cur] = true;
  DepthFirstSearch(cur + 1, countt + 1, probability * probabilities[cur]);
  vis[cur] = false;
  DepthFirstSearch(cur + 1, countt, probability * (1.0 - probabilities[cur]));
}