HDU-4336 Card Collector

题目链接

Translate：

有 (n) 种卡片，一包零食里会有一张卡片，其中是卡片 (i) 的概率是 (p_i)。

求集齐全部卡片的期望购买零食数。

(1leq Nleq 20,sum pleq 1)

Solution:

设 (f_{S}) 为从已有的状态为 (S) 时开始，集齐全部全部卡片的期望购买零食数，显然有：

前半部分是抽中原先没有的，后半部分是抽中已经有的或者没抽中，最后 (+1) 是因为购买了一包零食。

[f_S=sum_{i otin S}f_{Scup{i}}p_i+(1-sum_{i otin S}p_i)f_S+1 \ (sum_{i otin S}p_i)f_S = (sum_{i otin S}f_{Scup{i}}p_i)+1 ]

状压dp即可。

参考代码

#include<iostream>
#include<cstdio>
#include<algorithm>
namespace do_while_true {
	#define ld double
	#define ll long long
	#define re register
	#define pb push_back
	#define fir first
	#define sec second
	#define pp std::pair
	#define mp std::make_pair
	const ll mod = 998244353;
	template <typename T>
	inline T Max(T x, T y) { return x > y ? x : y; }
	template <typename T>
	inline T Min(T x, T y) { return x < y ? x : y; }
	template <typename T>
	inline T Abs(T x) {	return x < 0 ? -x : x; }
	template <typename T>
	inline T& read(T& r) {
		r = 0; bool w = 0; char ch = getchar();
		while(ch < '0' || ch > '9') w = ch == '-' ? 1 : 0, ch = getchar();
		while(ch >= '0' && ch <= '9') r = r * 10 + (ch ^ 48), ch = getchar();
		return r = w ? -r : r;
	}
	template <typename T>
	inline T qpow(T x, T y) {
		re T sumq = 1; x %= mod;
		while(y) {
			if(y&1) sumq = sumq * x % mod;
			x = x * x % mod;
			y >>= 1;
		}
		return sumq;
	}
}
using namespace do_while_true;

const int N = 21;

int n;

ld p[N], f[2100000];

void solve() {
	for(int i = 1; i <= n; ++i) scanf("%lf", &p[i]);
	f[(1 << n)-1] = 0;
	for(int i = (1 << n)-2; ~i; --i) {
		ld s1 = 0, s2 = 0;
		for(int j = 1; j <= n; ++j)
			if(((1 << (j-1)) & i) == 0)
				s1 += p[j], s2 += f[i | (1 << (j-1))] * p[j];
		f[i] = (s2 + 1) / s1;
	}
	printf("%.4lf
", f[0]);
}

signed main() {
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	#endif
//	int T = 1;
//	read(T);
	while(~scanf("%d", &n)) solve();
	fclose(stdin);
	return 0;
}