[HDU4336]Card Collector

题目大意

你每次按照概率得到给定卡片中的一张或什么都不得到

求得到所有卡片的步数期望

(nleq20)

解题思路

最值反演

(min(S))代表得到至少一张卡片的期望步数

(max(S))代表得到所有卡片的期望步数

容易得到(min(S)=frac{1}{sum_{x in S}{P_x}})

根据最值反演公式(max(S)=sum_{S' subseteq S}{min(S')cdot(-1)^{|S'|+1}})

于是答案就是(max(Full))

那么dfs暴力枚举每一个子集可以做到(O(2^n))复杂度

要注意的就是空集不能够计算进去

#include<iostream>
#include<cstdio>

const double eps=1e-9;

int n;
double p[30];
double ans;

void dfs(int now,double P,int flag){
	if (now>n){
		if (P>eps) ans+=flag/P;
		return;
	}
	dfs(now+1,P,flag);
	dfs(now+1,P+p[now],-flag);
}

int main(){
	while (scanf("%d",&n)==1){
		ans=0;
		for (int i=1;i<=n;i++) scanf("%lf",&p[i]);
		dfs(1,0,-1);
		printf("%.9lf
",ans);
	}
}