【HDU4336】Card Collector（Min-Max容斥）

题面

题解

原来似乎写过一种状压的做法，然后空间复杂度很不优秀。

今天来补一种神奇的方法。

给定集合\(S\)，设\(max\{S\}\)为\(S\)中的最大值，\(min\{S\}\)为集合\(S\)中的最小值。

那么我们可以得到：

\(max\{S\}=\sum_{T\subseteq S}(-1)^{|T|+1}min\{T\}\)

证明的话，大概就是如果你钦定一个最小值，并且它强制出现，

如果枚举所有子集，不难证明除了最大值之外，任何一个数的出现次数都是\(2^k\)的形式。

并且子集大小的奇偶性一一对应。因此，除了最大值之外，任何一个值的贡献全部会互相抵消，最后剩下的值就只有最大值。

对于期望而言这样做也是正确的。

回到这道题目，我们\(max\{S\}\)表示集合中最晚出现的元素，\(min\)同理。

\(E(max\{S\})\)表示出现时间的期望。

那么我们要求的是\(E(max\{\)全集\(\})\)，那么利用\(min-max\)容斥，有：

\(E(max\{S\})=\sum_{T\subseteq S}(-1)^{|T|+1}E(min\{T\})\)

而\(E(min\{T\})=\frac{1}{\sum_{i\in T}p_i}\)

那么枚举子集，直接\(dfs\)实现就好了

#include<cstdio>

int n;

double p[20],ans;

void dfs(int x,double e,int opt)

{

	if(x>=n){if(e>1e-7)ans+=opt/e;return;}

	dfs(x+1,e,opt);dfs(x+1,e+p[x],-opt);

}

int main()

{

	while(scanf("%d",&n)!=EOF)

	{

		for(int i=0;i<n;++i)scanf("%lf",&p[i]);

		ans=0;dfs(0,0,-1);

		printf("%.6lf\n",ans);

	}

}

巴特西

【HDU4336】Card Collector（Min-Max容斥）

【HDU4336】Card Collector（Min-Max容斥）

题面

题解

最新文章

热门文章