hdu 4336 dp求期望（状态压缩）

题意：有n种卡片，吃零食的时候会吃到一些卡片，告诉你在一袋零食中吃到每种卡片

的概率，求搜集齐每种卡片所需要买零食的袋数的期望。

分析：n比较小，很自然的想到状态压缩DP

再分析一下转移过程的递推式就ok了

假设S状态中为1的数位表示还没有拿到的卡片，那么每次可能会
拿到这其中的某一张卡片，

也可能拿到原来已经拿到的卡片，

还可能一张卡片也拿不到

后两种情况的状态不变。
dp[0]=0;(表示每一种卡片都取完了，期望当然是0喽)
dp[S]=sum*dp[S]+p[x1]dp[S^(1< sum是后两种情况的概率之和
移项，化简即可得到dp[S]的表达式
最后输出dp[(1< [cpp]
#include
#include
double dp[1<<20];
double p[22];
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
double x=0;
for(int i=0;i {
scanf("%lf",&p[i]);
x+=p[i];
}
dp[0]=0;
for(int i=1;i<(1< {
double cnt=0;
double sum=0;
double s=0;
for(int j=0;j {
if(!(i&(1< {
sum+=p[j];
}
if(i&(1< {
s+=p[j]*dp[i^(1< }
}
sum+=1-x;
dp[i]=(s+1)/(1-sum);
}
printf("%.5lf\n",dp[(1< }
return 0;
}