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;  
} 

补充：软件开发 , C++ ,

上一个：线索二叉树
下一个：HDU 3501 Calculation 2 （欧拉函数||容斥原理）