用二进制数表示拿了多少cards,f[x]表示在当前状态下已经有了x,到达拿到所有cards还要多少步。
注意p1 + p2 + ... + pN <= 1,所以 disjoint sample space里面,取不到card也是一种case
f[x]=1+p0*f[x]+Σ(1-p[j])f[x]+Σ(1-p[j]k)f[x|(1<<k)]
j表示本次取到的card之前取到过了,所以还是下一个状态还是f[x],k表示本次取到的card之前没有取过,所以还是下一个状态是f[x|(1<<k)],+1是因为本次操作肯定会增加一个1,p0*f[x]表示当前没取到card,下一个状态还是f[x]。
#include<iostream> #include<stdio.h> #include<cstdio> #include<stdlib.h> #include<vector> #include<string> #include<cstring> #include<cmath> #include<algorithm> #include<stack> #include<queue> #include <ctype.h> using namespace std; //hdu 4336 int N; double p[25]; const int maxn=(1<<20)-1; double f[maxn]; int all; double p0; void run() { memset(f,0,sizeof(f)); f[all]=0; for(int x=all-1;x>=0;x--) { double den=0; double num=0; for(int k=0;k<N;k++) { if((x&(1<<k))==0)//k doesn't belong to x //之前写成了if(x&(1<<k)==0), 少了括号if条件判断不了,运算符优先级真实坑 { // cout<<" k: "<<k<<endl; num+=p[k]*f[x|(1<<k)]; } else if((x&(1<<k)))//k belongs to x 这边也要多加个括号,注意优先级 { den+=p[k]; } } // cout<<" num "<<num<<" "<<den<<endl; f[x]=(1+num)/(1-p0-den);//这里不用特判分母=0,因为=0的case是f[all] // cout<<x<<" "<<f[x]<<endl; } printf("%.4lf\n",f[0]);//虽然sample给的是三位小数,但是题目要求是1e-4,因为这个WA了。。 } int main() { freopen("input.txt","r",stdin); // freopen("data.txt","r",stdin); //freopen("out1.txt","w",stdout); while(scanf("%d",&N)!=EOF) { p0=1; for(int i=0;i<N;i++) { scanf("%lf",&p[i]); p0-=p[i];// p[0] means the probability that get no ball; } //cout<<p0<<endl; all=(1<<N)-1; run(); } return 0; }