hdoj 4336 Card Collector 【概率dp】

桃扇骨 2022-08-12 14:00 25阅读 0赞

题目：[hdoj 4336 Card Collector ][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]: http://acm.hdu.edu.cn/showproblem.php?pid=4336

发表评论取消回复

表情：

评论列表（有 0 条评论，25人围观）

还没有评论，来说两句吧...

相关阅读

相关概率期望dp

简易的入门：http://kicd.blog.163.com/blog/static/126961911200910168335852/ 大神的总结：http://blog

港控/mmm°/ 2023年08月17日 16:25/ 0 赞/ 116 阅读

相关（转）HDOJ4336 Card Collector --- 容斥原理 or 状压dp

Card Collector Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java

╰半夏微凉°/ 2023年07月04日 03:21/ 0 赞/ 1 阅读

相关烟花（概率dp）

https://ac.nowcoder.com/acm/problem/18200 分析： double x = 1.0000 - arr\[i\]; doubl

秒速五厘米/ 2023年01月13日 15:56/ 0 赞/ 220 阅读

相关算法提高概率计算（概率dp）

问题描述　　生成n个∈\[a,b\]的随机整数，输出它们的和为x的概率。输入格式　　一行输入四个整数依次为n，a，b，x，用空格分隔。输出格式　　输出一行包

缺乏、安全感/ 2022年09月28日 15:20/ 0 赞/ 213 阅读

相关 Hdu 4336 Card Collector (容斥原理循环)

题意：有n种卡片，每种卡片 i 出现的概率为 pi ，一袋小吃有可能没有卡片，但最多有一张，问集齐所有卡片需要购买小吃的袋数期望。思路：容斥原理，感觉循环写法更适合自己。

╰+攻爆jí腚メ/ 2022年08月26日 08:05/ 0 赞/ 154 阅读

相关 HDU 5159 Card （概率DP）

HDU 5159 Card （概率DP）：[http://acm.hdu.edu.cn/showproblem.php?pid=5159][http_acm.hdu.edu.c

ゝ一纸荒年。/ 2022年08月22日 00:03/ 0 赞/ 198 阅读

相关 hdoj 4336 Card Collector 【概率dp】

题目：[hdoj 4336 Card Collector ][hdoj 4336 Card Collector] 题意：集齐卡片抽大奖，每个卡片概率，及其卡片个数，

桃扇骨/ 2022年08月12日 14:00/ 0 赞/ 26 阅读

相关 hdoj 2602 Bone Collector【01背包】

Bone Collector Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K

深藏阁楼爱情的钟/ 2022年08月09日 06:45/ 0 赞/ 19 阅读

相关 hdu 4336 求概率状态压缩+容斥原理

Card Collector

傷城~/ 2022年07月28日 01:46/ 0 赞/ 153 阅读

相关 hdoj3709（数位dp）

题目链接：https://vjudge.net/problem/HDU-3709 题意：求出\[l,r\]中的平衡数，平衡数即存在一个中心点使得两边的力矩和相等。思路：首

桃扇骨/ 2021年12月21日 01:07/ 0 赞/ 317 阅读