[HDU4336]Card Collector

2018/03/29 13:17
阅读数 28

vjudge #题意 有$n$张卡片,每一次你有$p_i$的概率买到第$i$张卡。求买到所有卡的期望购买次数。 $n\le20,\sum p_i\le1$ #sol $n\le20$那就一定是状压了吧。 设$f_s$表示已经买到了集合$s$后的期望购买次数。显然转移方程式长这样: $f_s=\sum_{i\notin{S}}f_{s|{i}}*p_i+(1-\sum_{i\notin{S}}p_i)f_s+1$ 这个转移是个$DAG$可以直接$dp$。复杂度$O(2^nn)$。

#include<cstdio>
#include<algorithm>
using namespace std;
int n,all;double p[20],f[1<<20];
int main()
{
	while (scanf("%d",&n)!=EOF)
	{
		for (int i=0;i<n;++i) scanf("%lf",&p[i]);
		all=(1<<n)-1;f[all]=0;
		for (int i=all-1;~i;--i)
		{
			double sum=0;f[i]=0;
			for (int j=0;j<n;++j)
				if (~i&(1<<j)) f[i]+=p[j]*f[i|(1<<j)],sum+=p[j];
			f[i]=(f[i]+1)/sum;
		}
		printf("%.4lf\n",f[0]);
	}
	return 0;
}

然而还有一个方法做。 用到一个叫什么鬼min-max容斥的东西。 就是一个式子: $$E(\max{x_1,x_2...x_n})=\sum_{S}(-1)^{|S|+1}E(\min_{i\in{S}}{x_i})$$ 其中$x_i$表示买到第$i$张卡片的期望购买次数,显然的,$\min_{i\in{S}}x_i=\frac{1}{\sum_{i\in{S}}p_i}$ 所以你只要直接$dfs$就可以做到$O(2^n)$同时空间复杂度$O(n)$了。

#include<cstdio>
#include<algorithm>
using namespace std;
int n;double p[20],ans;
void dfs(int i,double sum,double opt)
{
	if (i==n)
	{
		if (sum>1e-9) ans+=opt/sum;
		return;
	}
	dfs(i+1,sum+p[i],-opt);
	dfs(i+1,sum,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("%.4lf\n",ans);
	}
	return 0;
}
展开阅读全文
sol
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部