题目链接：点击打开链接
题意：
有n种卡片，每吃一包方便面都有一定概率获得其中一种卡片（也可能不获得卡片）
问集齐n张召唤神龙需要吃的方便面包数的期望。
思路：
dp[i] 表示已经拥有卡片的状态为i，， 要拥有所有卡片还需要吃的方便面包数的期望
显然 dp[(1<<n)-1] = 0; (已经拥有卡片就不用吃了嘛）
而答案就是dp[0];
用样例二举例，下面dp方程内直接用二进制表示，为了方便观察，我们用最高位表示第一张卡片（P1=0.1),最低位表示第n张卡片(P2=0.4)
dp[01] = (dp[01]+ 1)* P + (dp[11]+1) *P2 //其中P表示吃不到新卡片的概率
Obviously, P+P2 = 1
=> dp[01] = dp[01] * P + dp[11] * P2 + 1;
再移项得到
=> dp[01] = (dp[11] * P2+1) / (1-P);
所以dp[01] = 1/0.4 = 2.5, 同理得dp[10] = 10;
dp[00] = dp[00]*0.5 + dp[01] * 0.1 + dp[10] * 0.4 + 1
=>dp[00] = 10.5
（当然代码里是低位表示第一张卡片）
会发现其实 1-P 就是上面所有 dp[x] * px 的px的和。。
#include<cstdio> #include<cstring> const int LMT=1<<20; double dp[LMT+1],p[25]; int main(void) {int i,n,lim,j;double tem;while(~scanf("%d",&n)){memset(dp,0,sizeof(dp));for(i=0;i<n;i++)scanf("%lf",&p[i]);lim=(1<<n)-1;tem=0;for(i=lim-1;i>=0;i–){tem=0.0;dp[i]++;for(j=0;j<n;j++)if(!(i&(1<<j))){dp[i]+=dp[i|(1<<j)]*p[j];tem+=p[j];}dp[i]/=tem;}printf("%.4lf\n",dp[0]);}return 0; }
（当然代码里是低位表示第一张卡片）
车到山前必有路，没路可以先开路，开路就得有乐观，
