首页 > 其他分享 >[ZR] WI

[ZR] WI

时间:2024-11-08 17:32:23浏览次数:3  
标签:frac 抽到 复杂度 WI 单调 考虑 ZR

source:zr 二十联测 day16 B

题意

给定 \(n\) 个数 \(a_i\)。

每次你需要花费 \(c\) 在剩余的数中均匀随机获得一个数,你可以选择留下这个数,此时游戏结束且得分为该数值;否则将这个数扔掉(但不放回),然后游戏继续。

求最大期望。要求时间复杂度 \(O(n)\)。

分析

将 \(a_i\) 降序排序。

首先需要发现,我们的最优策略一定形如 \(t_1,t_2,\cdots,t_k\),表示我在第 \(i\) 次游戏时抽到了下标 \(\le t_i\) 的数就见好就收,否则把数扔掉。其次一定有 \(t_i\) 单调不升。

考虑设计一个暴力 DP。设 \(f_{i,j}\) 表示剩下 \(i\) 个数,当前极长的没被删的前缀长度为 \(j\) 的最大期望。由于 \(t_i\) 单调不升,所以在 \(i-1\) 决策完之后,\(>t_{i-1}\) 的那些数如果抽到是肯定要丢的。转移考虑抽到的是肯定要丢的还是可以决策留不留的,转移方程:\(f_{i,j}=\frac{i-j}{i}f_{i-1,j}+\frac{\sum_{k=1}^j\max(a_k,f_{i-1,k-1})}{i}-c\)。

裸实现时间复杂度 \(O(n^3)\)。由于状态数已经达到了平方级别,所以考虑怎么压状态。

考虑到对于那些一定要丢的数,我们并不关心具体选了哪个,所以我们不妨这么考虑:如果删了一定要丢的数,钦定它选了最小的那个数,据此设计 DP 状态为 \(f_i\) 表示剩了 \(i\) 张牌的最大期望。转移考虑枚举 \(t_i=p\):\(f_{i}=\frac{i-p}{i}f_{i-1}+\frac{\sum_{i=1}^p s_i}{i}\)。复杂度平方。

考虑优化。发现 \(p\) 指针右移造成的增量为 \(f_{i-1}-a_p\),由于 \(a_p\) 单调,所以我们实际上只需要找到第一个 \(\ge f_{i-1}\) 的 \(a_p\) 即可。若采用二分复杂度带老哥,但是发现 \(f_i\) 本身也是单调的,据此可以双指针,复杂度线性。

标签:frac,抽到,复杂度,WI,单调,考虑,ZR
From: https://www.cnblogs.com/dcytrl/p/18535463

相关文章

  • windows基础
    windows基础1、windows&linux微软windows操作系统,俗称windows文件系统linux:fhs目录结构,块设备挂载到目录(一切都是文件)win:以驱动器盘符起始,或通过目录挂载分区路径格式linux:/开始,区分大小写(左斜线)win:\分隔路径,不区分大小写(右斜线)系统配置linux:etc/和/proc(存储在信息......
  • 【亲测】Adobe Media Encoder(ME)软件下载win版中文版快速安装使用
    目录一、软件简介1.1核心功能1.2集成与工作流1.3用户界面和易用性二、下载与安装2.1下载软件2.2安装过程2.3配置和首次使用三、系统要求3.1操作系统3.2硬件要求3.3其他要求一、软件简介AdobeMediaEncoder(简称ME)是一个强大的视频和音频编码软件,广泛......
  • windows上好用的11款工具
    Windows必备的11款工具你有用到过吗1、Quicker一个超级强大的办公软件,能够一键调出所有的应用程序。不管是工作还是学习经常用到的程序都能用它一键快速启动,包括:翻译、文本处理、图片操作、文件处理,剪贴板、OCR文字识别、wWindows资源管理器、office文档、聊天对话框等。使......
  • Windows安装Python开发环境
    一、下载安装包1、下载最新版本:https://www.python.org/downloads/2、历史版本下载https://www.python.org/ftp/python/二、安装1、点击安装程序,如下图勾选Addpython.exetoPath,点击InstallNow,或选择下面的自定义安装注:勾选Addpython.exetoPath会自动配置环境变量......
  • 监控 Windows 更新补丁安装过程中的文件夹和文件,可以通过 PowerShell 监控 Windows 更
    监控Windows更新补丁安装过程中的文件夹和文件,可以通过PowerShell监控Windows更新的日志文件夹、注册表或其他相关位置。Windows更新会在多个地方生成日志和文件,下面提供了一个使用PowerShell监控Windows更新相关路径、文件夹及文件的示例。监控Windows更新相关的文......
  • windows搭建syncthing中继服务器和发现服务器
    软件准备1.stdiscosrv:发现服务器,下载地址https://github.com/syncthing/discosrv/releases2.strelaysrv:中继服务器,下载地址 https://github.com/syncthing/relaysrv/releases3.syncthing:文件同步程序,下载地址 https://syncthing.net/downloads根据自身需要下载相应系统相应......
  • win10找不到vcruntime140_1.dll,无法继续执行代码的解决方法
    vcruntime140_1.dll是微软VisualC++RedistributableforVisualStudio的一个动态链接库(DLL)文件。它是运行由VisualStudio2015及更高版本编译的C++应用程序所必需的。该DLL文件包含了支持C++标准库和Microsoft特定扩展功能的运行时函数,对于Windows应用程序......
  • linux新增物理卷,扩容逻辑分区,出现WARNING: xfs signature detected on /dev/vdb at of
    linux新增物理卷出现WARNING:xfssignaturedetectedon/dev/vdbatoffset0.Wipeit?[y/n]:标识这个/dev/vdb磁盘已经从0位置被标记为xfs类型的文件系统报错解释:这条信息表示在设备/dev/vdb上检测到了XFS文件系统的签名。通常情况下,这可能意味着分区/dev/vdb已被......
  • C:\Windows\System32\spp\store 文件夹是 Windows 操作系统中与激活和许可证管理
    C:\Windows\System32\spp\store文件夹是Windows操作系统中与激活和许可证管理相关的一个重要文件夹。该文件夹存储了与Windows激活过程相关的信息、许可证密钥、许可证的状态等数据。具体来说,它主要涉及SoftwareProtectionPlatform(SPP),即软件保护平台。1. 什么是SPP......
  • WINFORM简单套打程序示例
    1、软件界面(printDialog和printdocument两个控件显示在下方)  2、主要代码usingSystem;usingSystem.Collections.Generic;usingSystem.ComponentModel;usingSystem.Data;usingSystem.Drawing;usingSystem.Linq;usingSystem.Text;usingSystem.Threading.Tas......