题目:http://acm.hdu.edu.cn/showproblem.php?pid=4336
bzoj 4036 的简单版,Min-Max 容斥即可。
代码如下:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef double db;
int const xn=,xm=(<<)+;
int n,bin[xn];
db p[xn],mn[xm];
int cal(int s){int ret=; while(s)ret+=(s&),s>>=; return ret;}
int main()
{
bin[]=; for(int i=;i<=;i++)bin[i]=(bin[i-]<<);
while(~scanf("%d",&n))
{
int mx=(<<n);
for(int i=;i<=n;i++)scanf("%lf",&p[i]);
for(int T=;T<mx;T++)
{
db sum=;
for(int i=;i<=n;i++)if(T&bin[i-])sum+=p[i];
mn[T]=/sum;
}
db ans=;
for(int T=;T<mx;T++)ans+=mn[T]*((cal(T)&)?:-);
printf("%.10f\n",ans);
}
return ;
}