hdu 4336 dp求期望（狀態壓縮）

題意：有n種卡片，吃零食的時候會吃到一些卡片，告訴你在一袋零食中吃到每種卡片

的概率，求搜集齊每種卡片所需要買零食的袋數的期望。

分析：n比較小，很自然的想到狀態壓縮DP

再分析一下轉移過程的遞推式就ok了

假設S狀態中為1的數位表示還沒有拿到的卡片，那麼每次可能會
拿到這其中的某一張卡片，

也可能拿到原來已經拿到的卡片，

還可能一張卡片也拿不到

後兩種情況的狀態不變。
dp[0]=0;(表示每一種卡片都取完了，期望當然是0喽)
dp[S]=sum*dp[S]+p[x1]dp[S^(1<<x1)]+p[x2]dp[S^(1<<x2)].....+1;
sum是後兩種情況的概率之和
移項，化簡即可得到dp[S]的表達式
最後輸出dp[(1<<n)-1]表示每一種卡片都沒取時候的期望
[cpp] 
#include<cstdio> 
#include<cstring> 
double dp[1<<20]; 
double p[22]; 
int main() 
{ 
    int n; 
    while(scanf("%d",&n)!=EOF) 
    { 
        double x=0; 
        for(int i=0;i<n;i++) 
        { 
            scanf("%lf",&p[i]); 
            x+=p[i]; 
        } 
        dp[0]=0; 
        for(int i=1;i<(1<<n);i++) 
        { 
            double cnt=0; 
            double sum=0; 
            double s=0; 
            for(int j=0;j<n;j++) 
            { 
                if(!(i&(1<<j))) 
                { 
                    sum+=p[j]; 
                } 
                if(i&(1<<j)) 
                { 
                      s+=p[j]*dp[i^(1<<j)]; 
                } 
            } 
            sum+=1-x; 
            dp[i]=(s+1)/(1-sum); 
        } 
        printf("%.5lf\n",dp[(1<<n)-1]); 
    } 
    return 0;  
}