题意:
有N(1<=N<=20)张卡片,每包中含有这些卡片的概率为p1,p2,````pN.
每包至多一张卡片,可能没有卡片。
求需要买多少包才能拿到所以的N张卡片,求次数的期望。
转移方程: f[s] = 1 + ((1-segma{ p[i] })f[s]) + (segma{ p[j]*f[s] }) + (segma{ p[k]*f[s|(1<<k)] })
移项可得:
segma{ p[i] }f[s] = 1 + segma{ p[i]*f[s|(1<<i) },i=第i 种卡片没有收集到
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
using namespace std;
#define MOD 1000000007
const double eps=1e-;
#define cl(a) memset(a,0,sizeof(a))
#define ts printf("*****\n");
const int MAXN=;
int n,m,tt;
double a[MAXN];
double dp[<<];
int main()
{
int i,j,k;
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
while(scanf("%d",&n)!=EOF)
{
double tt=;
for(i=;i<n;i++) scanf("%lf",&a[i]),tt+=a[i];
dp[(<<n)-]=;
tt=-tt;
for(i=(<<n)-;i>=;i--)
{
double sum=,x=;
for(j=;j<n;j++)
{
if(i&(<<j))
{
x+=a[j]; //出现的卡片原来有了
}
else
{
sum+=a[j]*dp[i|(<<j)];
}
}
dp[i]=sum/(-tt-x);
}
printf("%.5lf\n",dp[]);
}
return ;
}