【hdu 4336】Card Collector

· · 个人记录

题目描述

有 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();
    }
}