Acwing.4009 收集卡牌(期望dp)

题目

小林在玩一个抽卡游戏,其中有 n种不同的卡牌,编号为 1到 n。

每一次抽卡,她获得第 i种卡牌的概率为 pi。

如果这张卡牌之前已经获得过了,就会转化为一枚硬币。

可以用 k枚硬币交换一张没有获得过的卡。

小林会一直抽卡,直至集齐了所有种类的卡牌为止,求她的期望抽卡次数。

如果你给出的答案与标准答案的绝对误差不超过 10−4,则视为正确。

提示:聪明的小林会把硬币攒在手里,等到通过兑换就可以获得剩余所有卡牌时,一次性兑换并停止抽卡。

输入格式

输入共两行。

第一行包含两个用空格分隔的正整数 n,k,第二行给出 p1,p2,…,pn,用空格分隔。

输出格式

输出共一行,一个实数,即期望抽卡次数。

数据范围

对于 20% 的数据,保证 1≤n,k≤5。 对于另外 20%的数据,保证所有 pi是相等的。 对于 100%的数据,保证
1≤n≤16,1≤k≤5,所有的 pi满足 pi≥110000,且 ∑ni=1pi=1。 注意,本题在官网必须保留
10位小数才能通过(可能是没加SPJ),在本网站无此问题,只要满足你给出的答案与标准答案的绝对误差不超过 10−4,则视为正确。

  • 输入样例1:
2 2
0.4 0.6
  • 输出样例1:
2.52

样例1解释

共有 2种卡牌,不妨记为 A和 B,获得概率分别为 0.4和 0.6,2枚硬币可以换一张卡牌。下面给出各种可能出现的情况:

第一次抽卡获得 A,第二次抽卡获得 B,抽卡结束,概率为 0.4×0.6=0.24,抽卡次数为 2。
第一次抽卡获得 A,第二次抽卡获得 A,第三次抽卡获得 B,抽卡结束,概率为 0.4×0.4×0.6=0.096,抽卡次数为 3。
第一次抽卡获得 A,第二次抽卡获得 A,第三次抽卡获得 A,用硬币兑换 B,抽卡结束,概率为 0.4×0.4×0.4=0.064,抽卡次数为 3。
第一次抽卡获得 B,第二次抽卡获得 A,抽卡结束,概率为 0.6×0.4=0.24,抽卡次数为 2。
第一次抽卡获得 B,第二次抽卡获得 B,第三次抽卡获得 A,抽卡结束,概率为 0.6×0.6×0.4=0.144,抽卡次数为 3。
第一次抽卡获得 B,第二次抽卡获得 B,第三次抽卡获得 B,用硬币兑换 A,抽卡结束,概率为 0.6×0.6×0.6=0.216,抽卡次数为 3。
因此答案是 0.24×2+0.096×3+0.064×3+0.24×2+0.144×3+0.216×3=2.52。

  • 输入样例2:
4 3
0.006 0.1 0.2 0.694
  • 输出样例2:
7.3229920752

题解

import java.text.DecimalFormat;
import java.util.*;

/**
 * @author amuya
 * @create 2024-04-10-19:46
 */
public class CollectCards {
    static int n,m;
    static int N=16;
    static int M=1<<N;
    //硬币不超过80,超过80直接结束
    static double f[][]=new double[M][N*5+1];
    static double p[]=new double[N+1];
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        n=scanner.nextInt();
        m=scanner.nextInt();
        for(int i=1;i<=n;i++){
            p[i]=scanner.nextDouble();
        }

        for(int i=0;i<M;i++) Arrays.fill(f[i],-1);
        DecimalFormat df=new DecimalFormat("#.##########");
        String s=df.format(dp(0,0,n));
        System.out.println(s);
    }
    public static double dp(int a,int b,int r){
        if(f[a][b]>=0) return f[a][b];
        if(b>=r*m) {
            f[a][b]=0;
            return 0;
        }


        f[a][b]=0;

        for(int i=0;i<n;i++){
            if((a&(1<<i))>0){
                f[a][b]+=p[i+1]*(dp(a,b+1,r)+1);
            }else{
                f[a][b]+=p[i+1]*(dp(a|(1<<i),b,r-1)+1);
            }
        }

        return f[a][b];
    }
}

思路

使用状态压缩DP可以存储所有情况,再通过数学推导推导出递推公式,具体推导过程如下图。
其中状态转移数组有两个参数 a(压缩状态),b(硬币数)(可有可无,仅方便计算),值为从当前状态到抽完所需要抽数的期望。
然后根据下列推导,当前期望等于接下来所有可能的概率乘以其对应的期望+1,为什么加1,因为下一种情况必然多抽了一次。再根据数学推导得到状态转移方程。

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/533248.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

2024大模型落地应用案例集(免费下载)

【1】扫码关注本公众号 【2】私信发送 2024大模型落地应用案例集 【3】获取本方案PDF下载链接&#xff0c;直接下载即可。

初识C++之内联函数 auto关键字

初识C之内联函数 auto关键字 文章目录 初识C之内联函数 auto关键字一、 内联函数1.1 定义1.2 应用1.3 特性 二、auto关键字2.1 简介2.2 auto的详细使用2.3 范围for&#xff08;C&#xff09;2.4 注意事项 一、 内联函数 1.1 定义 以inline修饰的函数叫做内联函数&#xff0c;…

UDP实现Mini版在线聊天室

实现原理 只有当客户端先对服务器发送online消息的时候&#xff0c;服务器才会把客户端加入到在线列表。当在线列表的用户发消息的时候&#xff0c;服务器会把消息广播给在线列表中的所有用户。而当用户输入offline时&#xff0c;表明自己要下线了&#xff0c;此时服务器把该用…

跨域问题一文解决

&#x1f4dd;个人主页&#xff1a;五敷有你 &#x1f525;系列专栏&#xff1a;Vue ⛺️稳中求进&#xff0c;晒太阳 一、为什么会出现跨域的问题&#xff1f; 是浏览器的同源策略&#xff0c;跨域也是因为浏览器这个机制引起的&#xff0c;这个机制的存在还是在于安全…

【MATLAB源码-第6期】基于matlab的QPSK的误码率BER和误符号率SER仿真。

1、算法描述 QPSK&#xff0c;有时也称作四位元PSK、四相位PSK、4-PSK&#xff0c;在坐标图上看是圆上四个对称的点。通过四个相位&#xff0c;QPSK可以编码2位元符号。图中采用格雷码来达到最小位元错误率&#xff08;BER&#xff09; — 是BPSK的两倍. 这意味著可以在BPSK系统…

利用DataX工具,实现MySQL与OceanBase的数据同步实践

数据迁移是经常遇到的需求&#xff0c;市面上为此提供了众多同步工具。这里将为大家简要介绍DataX的使用。DataX 是阿里云 DataWorks数据集成 的开源版本&#xff0c;它作为离线数据同步的工具/平台&#xff0c;在阿里巴巴集团内部被广泛应用。DataX 能够实现多种异构数据源之间…

图书馆自习室|基于SSM的图书馆自习室座位预约小程序设计与实现(源码+数据库+文档)

图书馆自习室目录 基于SSM的图书馆自习室座位预约小程序设计与实现 一、前言 二、系统设计 三、系统功能设计 1、小程序端&#xff1a; 2、后台 四、数据库设计 五、核心代码 六、论文参考 七、最新计算机毕设选题推荐 八、源码获取&#xff1a; 博主介绍&#xff1a…

[opencv]VideoWriter写出fourcc格式

fourcc支持的格式 fourcc全名Four-Character Codes&#xff0c;四字符代码&#xff0c;该编码由四个字符组成 cv2.VideoWriter_fourcc(O,O,O,O) cv2.VideoWriter_fourcc(*OOOO) 通常写法有上述两种形式&#xff0c;O代表一个字符&#xff0c;通常有 支持avi格式的有&#…

麒麟KOS删除鼠标右键新建菜单里不需要的选项

原文链接&#xff1a;麒麟KOS删除鼠标右键新建菜单里不需要的选项 Hello&#xff0c;大家好啊&#xff01;在日常使用麒麟KOS操作系统时&#xff0c;我们可能会发现鼠标右键新建菜单里包含了一些不常用或者不需要的选项。这不仅影响我们的使用效率&#xff0c;也让菜单显得杂乱…

【C++学习】C++11新特性(第一节)

文章目录 ♫一.文章前言♫二.C11新特性♫一.统一的列表初始化♫二.std::initializer_list♫三.声明♫四.decltype关键字♫五.nullptr♫六.新增加容器---静态数组array、forward_list以及unordered系列♫6.1unordered_map与unoredered_set♫6.2array♫6.3 forward_list&#xff…

上海亚商投顾:创业板指低开低走 低空经济概念股尾盘拉升

上海亚商投顾前言&#xff1a;无惧大盘涨跌&#xff0c;解密龙虎榜资金&#xff0c;跟踪一线游资和机构资金动向&#xff0c;识别短期热点和强势个股。 一.市场情绪 三大指数昨日集体调整&#xff0c;沪指午后跌超1%&#xff0c;深成指、创业板指盘中跌超2%&#xff0c;尾盘跌…

计算机视觉——基于深度学习UNet实现的复杂背景文档二值化算法实现与模型训练

1. 引言 阈值分割可以被视为一个分类问题&#xff0c;通常涉及两个类别&#xff0c;这也是为什么阈值分割也被称为二值化。对于文档图像&#xff0c;我们期望阈值算法能够正确地将墨水分类为黑色&#xff0c;将纸张分类为白色&#xff0c;从而得到二值化图像。对于数字灰度图像…

腾讯云人脸服务开通详解:快速部署,畅享智能体验

请注意&#xff0c;在使用人脸识别服务时&#xff0c;需要确保遵守相关的法律法规和政策规定&#xff0c;保护用户的合法权益&#xff0c;并依法收集、使用、存储用户信息。此外&#xff0c;腾讯云每个月会提供一定次数的人脸识别调用机会&#xff0c;对于一般的小系统登录来说…

头歌-机器学习 第11次实验 softmax回归

第1关&#xff1a;softmax回归原理 任务描述 本关任务&#xff1a;使用Python实现softmax函数。 相关知识 为了完成本关任务&#xff0c;你需要掌握&#xff1a;1.softmax回归原理&#xff0c;2.softmax函数。 softmax回归原理 与逻辑回归一样&#xff0c;softmax回归同样…

(三)、PTP时间精确协议如何工作的【Part1】

1、精确时钟需要校准 一个自由运行的时钟&#xff0c;本身每次的频率也不是绝对一致的&#xff08;每次频率都会有细微的差异&#xff09;&#xff0c;相位也是未知的。时间从来不是理想的&#xff0c;想到达到一个相对理想的准确时间&#xff0c;必须对时间进行调整&#xff0…

Electron 桌面端应用的使用 ---前端开发

Electron是什么&#xff1f; Electron是一个使用 JavaScript、HTML 和 CSS 构建桌面应用程序的框架。 嵌入 Chromium 和 Node.js 到 二进制的 Electron 允许您保持一个 JavaScript 代码代码库并创建 在Windows上运行的跨平台应用 macOS和Linux——不需要本地开发 经验。 入门…

2024.4.8Morris中序遍历(线索二叉树)学习

这次博主在学习完知识点和代码之后&#xff0c;准备对这个知识重新进行整理总结。站在一个初学者的角度来看待这个知识点&#xff0c;在他人的讲解基础上加一点点自己的理解&#xff0c;并记录下来。以加深自己的理解&#xff0c;并且希望能够帮助到你。博主是一个初学者&#…

马云最新发声:AI时代刚刚到来,一切才刚开始,我们正当其时!

大家好&#xff0c;我是木易&#xff0c;一个持续关注AI领域的互联网技术产品经理&#xff0c;国内Top2本科&#xff0c;美国Top10 CS研究生&#xff0c;MBA。我坚信AI是普通人变强的“外挂”&#xff0c;所以创建了“AI信息Gap”这个公众号&#xff0c;专注于分享AI全维度知识…

原码一位乘法

王道考研ppt总结&#xff1a; 个人理解&#xff1a; 原码一位乘法&#xff1a; 结果符号的确定&#xff1a;符号位异或&#xff0c;很好理解 数值位绝对值相乘 小数的乘法&#xff1a; 小学乘法的规则是&#xff1a;乘数的每一位和被乘数进行相乘&#xff0c;然后作为数积&…

labelImg将图像标签显示到界面

打开View的显示类别 但是颜色不够清晰&#xff0c;我想自己定制 我的象棋红色和黑色两种。并且把字体方法一些。 可以看到 color self.select_line_color if self.selected else self.line_color参考&#xff1a;https://blog.csdn.net/qq_41082953/article/details/10330225…