题目大意
有N(1<=N<=20)张卡片,每包中含有这些卡片的概率为p1,p2,````pN.
每包至多一张卡片,可能没有卡片。
求需要买多少包才能拿到所以的N张卡片,求次数的期望。
显然,这是一道概率dp,容斥原理也可以写
算概率一般是正推,算期望一般是逆推
代码实现
#include<cstdio>
#include<algorithm>
using namespace std;
const int mx=22;
double p[mx],dp[1<<mx];
int n;
int main(){
while(scanf("%d",&n)!=EOF){
double psum=0;
for(int i=0;i<n;i++){
scanf("%lf",&p[i]);
psum+=p[i];
}
psum=1-psum;//卡包内没有牌的概率
dp[(1<<n)-1]=0;
for(int i=(1<<n)-2;i>=0;i--){
double x=0,sum=1;//转移到下一状态,必然需要买一包卡包
for(int j=0;j<n;j++){
if(i&(1<<j))x+=p[j];
else sum+=p[j]*dp[i|(1<<j)];
}
dp[i]=sum/(1-psum-x);
//减去卡包内没有牌或有重复牌的情况
}
printf("%.5lf\n",dp[0]);
}
}