首页 > 其他 > 详细

hdu 4336 概率dp

时间:2015-04-14 00:12:12      阅读:152      评论:0      收藏:0      [点我收藏+]

题意:
有N(1<=N<=20)张卡片,每包中含有这些卡片的概率为p1,p2,````pN.
每包至多一张卡片,可能没有卡片。
求需要买多少包才能拿到所以的N张卡片,求次数的期望。

 

转移方程: f[s] = 1 + ((1-segma{ p[i] })f[s]) + (segma{ p[j]*f[s] }) + (segma{ p[k]*f[s|(1<<k)] })

 

移项可得:

 

        segma{ p[i] }f[s] = 1 + segma{ p[i]*f[s|(1<<i) },i=第i 种卡片没有收集到

 

 

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<queue>
 7 #include<map>
 8 using namespace std;
 9 #define MOD 1000000007
10 const double eps=1e-5;
11 #define cl(a) memset(a,0,sizeof(a))
12 #define ts printf("*****\n");
13 const int MAXN=22;
14 int n,m,tt;
15 double a[MAXN];
16 double dp[1<<22];
17 int main()
18 {
19     int i,j,k;
20     #ifndef ONLINE_JUDGE
21     freopen("1.in","r",stdin);
22     #endif
23     while(scanf("%d",&n)!=EOF)
24     {
25         double tt=0;
26         for(i=0;i<n;i++)    scanf("%lf",&a[i]),tt+=a[i];
27         dp[(1<<n)-1]=0;
28         tt=1-tt;
29         for(i=(1<<n)-2;i>=0;i--)
30         {
31             double sum=1,x=0;
32             for(j=0;j<n;j++)
33             {
34                 if(i&(1<<j))
35                 {
36                     x+=a[j];        //出现的卡片原来有了
37                 }
38                 else
39                 {
40                     sum+=a[j]*dp[i|(1<<j)];
41                 }
42             }
43             dp[i]=sum/(1-tt-x);
44         }
45         printf("%.5lf\n",dp[0]);
46     }
47     return 0;
48 }

 

hdu 4336 概率dp

原文:http://www.cnblogs.com/cnblogs321114287/p/4423576.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!