Always Firmly on OI

【hdu 4336】Card Collector

2018-12-24 19:01:48


题目描述

有 $n$ 种卡片,每一秒都有 $p_i$ 的概率获得一张第 $i$ 种卡片,求每张卡片都至少有一张的期望时间

$n \le 20$

题解

考虑 min-max 容斥, $E(\max(S))=\sum_{T \subseteq S}(-1)^{\mid T \mid + 1}E(\min(T))$

考虑 $E(\min(T))$ 的意义,即某个集合的至少获得其中一个元素的期望次数

由于每个元素的获得概率互不相关,因此:

$$E(\min(T))=(\sum\limits_{x \in T}p_x)1+(1-\sum\limits_{x \in T}p_x)(E(\min(T)) + 1)$$

即 $E(\min(T)) = \frac{1}{\sum\limits_{x \in T}p_x}$

然后枚举子集就行了……

题解

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 30;

int n; double p[N];

void sol() {
    for(int i = 1 ; i <= n ; ++ i) scanf("%lf", &p[i]);
    double res = 0;
    for(int s = 1 ; s < (1 << n) ; ++ s) {
        int cnt = 0; double sum = 0;
        for(int i = 1 ; i <= n ; ++ i) {
            if(s & (1 << (i - 1))) {
                ++ cnt;
                sum += p[i];
            }
        }
        res += (cnt & 1 ? 1.0 : -1.0) / sum;
    }
    printf("%.4f\n", res);
}

int main() {
    while(scanf("%d", &n) == 1) {
        sol();
    }
}