题目链接：

题意：

　　一共有n种卡片。每买一袋零食，有可能赠送一张卡片，也可能没有。

　　每一种卡片赠送的概率为p[i]，问你将n种卡片收集全，要买零食袋数的期望。

 

题解：

　　表示状态：

　　　　dp[state] = expectation

　　　　state表示哪些卡片已经有了

 

　　找出答案：

　　　　ans = dp[0]

　　　　什么都没有时的期望袋数

 

　　如何转移：

　　　　两种情况，要么得到了一张新的卡片，要么得到了一张已经有的卡片或者啥都没有。

　　　　　　dp[state] = ∑ (dp[state|(1<<i)]*p[i]) + dp[state]*(1 - ∑ p[i]) + 1

　　　　　　((state>>i)&1 == 0)

　　　　移项后：

　　　　　　dp[state] = ( ∑ (dp[state|(1<<i)]*p[i]) + 1 ) / ∑ p[i]

 

　　边界条件：

　　　　dp[(1<<n)-1] = 0

　　　　已经集全了。

 

AC Code:

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define MAX_N 25 5 #define MAX_S ((1<<20)+50) 6  7 using namespace std; 8  9 int n;10 double p[MAX_N];11 double dp[MAX_S];12 13 int main()14 {15     while(cin>>n)16     {17         for(int i=0;i
        
         =0;state--)20         {21             double sum=0;22             dp[state]=0;23             for(int i=0;i
         
          >i)&1))26                 {27                     dp[state]+=dp[state|(1<