hdu 4336 概率dp

题意：
有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 ;

 }