hdu4336 Expect to buy as many noodles as possible to collect all the cards (beginner)

Setting a state compression is the same expectation as 3853：http://www.cnblogs.com/xiao-xin/articles/4307653.html

Analyze the follow-up point carefully Bought and not bought can easily write the equation

1 #include
2 #include<string.h>
3 #include
4 using namespace std ;
5 double dp[1050005];
6 int main()
7 {
8 span> int i,j,size,next,n;
9 double zp,p[ 21];
10 while (~scanf(“%d“,&n))
11 {
12 for (i=0;i<n;i++) scanf(“ span>%lf“,&p[i]);
13 size=( 1<<n)-1;
14 memset(dp,0,sizeof(dp));
15 for (i=size-1;i>=0;i–)
16 {
17 zp=0.0;
18 for (j=0;j<n;j++)
19 if ((i&(1<<j))==0)
20 {
21 zp+=p[j];
22 next=(i|(1<<j));
23 dp[ i]+=p[j]*dp[next];
24 }
25 dp[i]=(dp[i]+1)/zp;
26 }
27 printf(“%.5lf\n“,dp[0]);
28 }
29 return 0;
30 }

View Code

Problem link ：http://acm.hdu.edu.cn/showproblem.php?pid=4336

Transfer: https:/ /www.cnblogs.com/xiao-xin/articles/4307674.html