首页 > 代码库 > hdu 4336 Card Collector
hdu 4336 Card Collector
有n种卡片,概率分别为p1...pn,p1+...+pn<=1
每个袋子最多一张卡片,也可以没有
这题巧妙的用到了整数的二进制
1 #include<iostream> 2 #include<string> 3 #include<cstdio> 4 #include<vector> 5 #include<queue> 6 #include<stack> 7 #include<algorithm> 8 #include<cstring> 9 #include<stdlib.h>10 using namespace std;11 #define pb push_back12 double dp[1<<21],p[22];13 int main(){14 int n;15 while(cin>>n){16 for(int i=0;i<n;i++)17 scanf("%lf",&p[i]);18 dp[(1<<n)-1]=0;19 for(int i=(1<<n)-2;i>=0;i--){20 double tmp=0;21 dp[i]=1;22 for(int j=0;j<n;j++){23 if(i&(1<<j)) continue; //i转化成二进制后,从右边开始数第j位是否为124 dp[i]+=dp[i|(1<<j)]*p[j];25 tmp+=p[j];26 }27 28 dp[i]/=tmp;29 }30 printf("%.6lf\n",dp[0]);31 }32 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。