hdu 4336 Card Collector

dp+状态压缩
 1 #include<cstdio>
 2 using namespace std;
 3 double p[23];
 4 double dp[1<<23];
 5 int main()
 6 {
 7     int n;
 8     while(scanf("%d",&n)!=EOF)
 9     {
10         for(int i=0; i<n; i++)
11             scanf("%lf",&p[i]);
12         dp[(1<<n)-1]=0;
13         for(int i=(1<<n)-2; i>=0; i--)
14         {
15             dp[i]=1.0;
16             double sum=0.0;
17             for(int j=0; j<n; j++)
18             {
19                 if(i&(1<<j)) continue;
20                 sum+=p[j];
21                 dp[i]+=dp[i|(1<<j)]*p[j];
22             }
23             //printf("%lf %lf==
",dp[i],sum);
24             dp[i]=dp[i]/sum;
25         }
26         printf("%lf
",dp[0]);
27     }
28     return 0;
29 }