首页 > > 程序设计 > C/C++ >

Card Collector HDU - 4336

2018-06-17 21:49:26来源：未知阅读 ()

ans[S]表示获得S的卡片次数的期望
考虑到达S前一次的卡片
1.获得一张已获得的期望是ans[S]*sum{p[i]|i在S中}
2.获得一张未获得的期望是sum{ans[S-i]*p[i]|i在S中}
3.未获得卡片期望是ans[S]*p[0]
因此ans[S]=ans[S]*(p[0]+sum{p[i]|i在S中})+sum{ans[S-i]*p[i]|i在S中}
ans[S]*(1-p[0]-sum{p[i]|i在S中})=sum{ans[S-i]*p[i]|i在S中}
ans[S]=sum{ans[S-i]*p[i]|i在S中}/(1-p[0]-sum{p[i]|i在S中})

X=ans[S]
Y=sum{(ans[S-i]+1)*p[i]|i在S中} 即获得一个未得的卡对期望的贡献
P2=p[0]+sum{p[i]|i在S中}) 即获得已得的卡或无卡的概率
那么Y+P2*(X+1)=X
P2*X+P2+Y=X
P2+Y=(1-P2)*X
X=(P2+Y)/(1-P2)

ans[S]表示全0到S所用步数的期望
考虑到达S前一次的卡片
1.未获得卡片/获得一张已获得的卡片期望是(p[0]+sum{p[S的某一个]})*(ans[S]+1)
01 0.6x+0.6 10 0.9x+0.9
2.获得一张未获得的期望是sum{p[S的某一个]*(ans[S-S的某一个]+1)}
01 0.1 10 0.4（错误答案花费7个小时）

以上全部都是错的。直觉上会让人想到将ans[S]定义为获得S的卡片的购买包数的期望，然而由于即使一包也不买，这个期望也不为0，导致非常难处理。

更好的方法是定义ans[S]为获得S的卡片到全部获得所用步数的期望。p[0]表示买一包不获得卡片的概率。考虑S状态后下一步：

1.未获得卡片/获得一张已获得的卡：期望是$(p[0]+sum\{p[S的某一个]\})*(ans[S]+1)$

样例1：0.9*11=9.9
样例2：

10 (0.5+0.4)*(ans[2]+1)
01 (0.5+0.1)*(ans[1]+1)
00 (0.5)*(ans[0]+1)

2.获得一张未获得的：期望是$sum\{p[S以外的i]*(ans[S+i]+1)\}$

样例1：0.1*1=0.1
样例2：
10 0.1*1=0.1
ans[2]=10
01 0.4*1=0.4
ans[1]=2.5
00 0.1*(ans[1]+1)+0.4*(ans[2]+1)=4.75
ans[0]=10.5

$(p[0]+sum\{p[S的某一个]\})*(ans[S]+1)+sum\{p[S以外的i]*(ans[S+i]+1)\}=ans[S]$

$(p[0]+sum\{p[S的某一个]\})*ans[S]+p[0]+sum\{p[S的某一个]\}+sum\{p[S以外的i]*(ans[S+i]+1)\}=ans[S]$

$(1-(p[0]+sum{p[S的某一个]}))*ans[S]=p[0]+sum{p[S的某一个]}+sum{p[S以外的i]*(ans[S+i]+1)}$

$ans[S]=(p[0]+sum\{p[S的某一个]\}+sum\{p[S以外的i]*(ans[S+i]+1)\})/(1-(p[0]+sum\{p[S的某一个]\}))$

 1 #include<cstdio>
 2 #include<cstring>
 3 double p[22],ans[1100000],tt;
 4 int n;
 5 int main()
 6 {
 7     int i,j;
 8     while(scanf("%d",&n)==1)
 9     {
10         p[0]=0;
11         for(i=1;i<=n;i++)
12         {
13             scanf("%lf",&p[i]);
14             p[0]+=p[i];
15         }
16         p[0]=1-p[0];
17         memset(ans,0,sizeof(ans));
18         for(i=(1<<n)-2;i>=0;i--)
19         {
20             tt=p[0];
21             for(j=1;j<=n;j++)
22                 if(i&(1<<(j-1)))
23                     tt+=p[j];
24                 else
25                     ans[i]+=p[j]*(ans[i|(1<<(j-1))]+1);
26             ans[i]+=tt;
27             ans[i]/=(1-tt);
28         }
29         printf("%lf\n",ans[0]);
30     }
31     return 0;
32 }