hdu4336 Card Collector 【最值反演】

2018/06/26 17:19
阅读数 12

#题目链接 hdu4336 #题解 ##最值反演 也叫做$min-max$容斥,在计算期望时有奇效 $$max{S} = \sum\limits_{T \in S} (-1)^{|T| + 1}min{T}$$

证明: 记$S = {a_i}$,其中对于$i < j$有$a_i < a_j$ 那么我们计算每一个$a_i$的贡献,有 $$ \begin{aligned} \sum\limits_{T \in S} (-1)^{|T| + 1}min{T} &= \sum\limits_{i = 1}^{n}a_i\sum\limits_{j = 0}^{n - i}(-1)^{j}{n - i \choose j}\ &= \sum\limits_{i = 1}^{n}a_i[n - i = 0]\ &= \sum\limits_{i = 1}^{n}a_i[n = i]\ &= a_n\ &= max{S} \end{aligned} $$ 证毕

对于此题,我们想要求出所有卡片集合$S$中最晚出现的卡片的期望,就转化为计算$S$的所有子集中最早出现的期望 对于一个集合$T$,显然出现一张卡片的期望为 $$\frac{1}{\sum\limits_{i \in T}p_i}$$ 枚举子集计算即可 复杂度$O(2^n)$

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<map>
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define mp(a,b) make_pair<int,int>(a,b)
#define cls(s) memset(s,0,sizeof(s))
#define cp pair<int,int>
#define LL long long int
using namespace std;
const int maxn = 25,maxm = 100005,INF = 1000000000;
double p[maxn],ans;
int n;
int main(){
	while (~scanf("%d",&n)){
		REP(i,n) scanf("%lf",&p[i]);
		int maxv = (1 << n) - 1; ans = 0;
		for (int s = 1; s <= maxv; s++){
			int cnt = 0; double tmp = 0;
			for (int e = s,j = 1; e; e >>= 1,j++)
				if (e & 1) cnt++,tmp += p[j];
			ans += (cnt & 1) ? 1 / tmp : -1 / tmp;
		}
		printf("%.8lf\n",ans);
	}
	return 0;
}

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部