Card Collector HDU - 4336

Card Collector HDU - 4336

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 }

http://blog.csdn.net/a1061747415/article/details/34481361

http://www.cnblogs.com/six-god/p/3580242.html