首页 > 代码库 > hdoj 4336 Card Collector 【概率dp】
hdoj 4336 Card Collector 【概率dp】
题目:hdoj 4336 Card Collector
题意:集齐卡片抽大奖,每个卡片概率,及其卡片个数,然后问你及其卡片要买卡片数量的期望。
分析:最多20张卡片,用状态压缩来表示是否拿了某个卡片。
比如现在有状态10010,表示拿了第2 3 5的状态下的期望。
我们要求它,我们可以先得到11010,10110,10011,的期望,然后乘以各自位没拿的概率就是总的期望。在除去总概率就是当前的期望,
不是很懂啊///数学智商有点捉急
AC代码:
#include <cstdio> #include <algorithm> #include <cstring> #include <string> #include <iostream> #include <vector> using namespace std; const int inf = 0x3f3f3f3f; const int N = 22; double dp[1<<N],p[N]; //dp[st] 表示状态st下拿为0状态的卡片的期望 int main() { int n; while(~scanf("%d",&n)) { double sum=0; for(int i=0;i<n;i++) scanf("%lf",&p[i]); dp[(1<<n)-1]=0; for(int st=(1<<n)-2;st>=0;st--) { double tt=0; for(int i=0;i<n;i++) { if(!(st&(1<<i))) dp[st]+=(dp[st|(1<<i)])*p[i],tt+=p[i]; } dp[st]/=tt; } printf("%.5lf\n",dp[0]); } return 0; }
hdoj 4336 Card Collector 【概率dp】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。