当前位置: 首页 > news >正文

D. Jellyfish and Mex - DP

题面

分析:

题目最终需要达到MEX位0,也就是从最开始的MEX变成0后m的最小值,可以设 d p i dp_i dpi表示当前MEX为 i i i时,m的最小值,那么就可以根据前一个状态推出后一个状态,也就是假如当前MEX是 i i i,那么对于1~ i i i之间的 j j j的所有每一种可能的MEX,都会有一个权值对应得到 d p j dp_j dpj取最小值得到最小的m值,状态转移方程为 d p j = m i n ( d p j , d p i + i ∗ a [ j ] ) dp_j = min(dp_j, dp_i + i * a[j]) dpj=min(dpj,dpi+ia[j]),最后 d p 0 dp_0 dp0也就是表示答案,但是第一次操作时m是0,所以第一次并没有加上初始的MEX,所以需要减去一个初始的MEX。

代码:

#include <bits/stdc++.h>using namespace std;
using ll = long long;const int inf = 0x3f3f3f3f;void solve() {int n;cin >> n;vector<int> a(n + 1);vector<ll> f(n + 1, inf);for(int i = 0; i < n; i ++) {ll x;cin >> x;if(x < n) a[x] ++;}int m = 0;while(a[m]) m ++;f[m] = 0;for(int i = m; i >= 1; i --) {for(int j = 0; j < i; j ++) {f[j] = min(f[j], f[i] + i * a[j]);}}cout << f[0] - m << "\n";
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin >> T;while(T --) {solve();}
}

相关文章:

D. Jellyfish and Mex - DP

题面 分析&#xff1a; 题目最终需要达到MEX位0&#xff0c;也就是从最开始的MEX变成0后m的最小值&#xff0c;可以设 d p i dp_i dpi​表示当前MEX为 i i i时&#xff0c;m的最小值&#xff0c;那么就可以根据前一个状态推出后一个状态&#xff0c;也就是假如当前MEX是 i i …...

奥斯卡·王尔德

奥斯卡王尔德 奥斯卡王尔德&#xff08;Oscar Wilde&#xff0c;1854年10月16日—1900年11月30日&#xff09;&#xff0c;出生于爱尔兰都柏林&#xff0c;19世纪英国&#xff08;准确来讲是爱尔兰&#xff0c;但是当时由英国统治&#xff09;最伟大的作家与艺术家之一&#xf…...

IDEA常用快捷键大全

整理了一些IDEA开发常用的快捷键&#xff1a; 快捷键组合实现效果psvm Tab键 / main Tab键public static void main(String[] args)sout Tab键System.out.println()Ctrl X删除当前行Ctrl D复制当前行AltInsert(或右键Generate)生成代码(如get,set方法,构造函数等)CtrlAltT…...

Java之多线程的综合练习二

练习六&#xff1a;多线程统计并求最大值 需求&#xff1a; 在上一题基础上继续完成如下需求&#xff1a; 每次抽的过程中&#xff0c;不打印&#xff0c;抽完时一次性打印(随机) 在此次抽奖过程中&#xff0c;抽奖箱1总共产生了6个奖项。 分别为&#xff1a;10,20,100,50…...

selenium下载安装 -- 使用谷歌驱动碰到的问题

安装教程参考: http://c.biancheng.net/python_spider/selenium.html 1. 谷歌浏览器和谷歌驱动版本要对应(但是最新版本谷歌对应的驱动是没有的,因此要下载谷歌历史其他版本): 谷歌浏览器历史版本下载: https://www.chromedownloads.net/chrome64win/谷歌浏览器驱动下载: http:…...

开放式耳机怎么选择、300之内最好的耳机推荐

开放式耳机凭借不入耳、不伤耳、安全更舒适的佩戴体验&#xff0c;得到了越来越多音乐爱好者和专业人士的青睐。开放式耳机不需要插入耳道&#xff0c;在佩戴时可以更加自然和轻松&#xff0c;减少了长时间佩戴引起的不适感&#xff0c;而且不会完全隔绝外界声音&#xff0c;用…...

git密码提交切换SSH提交

git保存密码 每次登录都要输入密码是显示繁琐&#xff0c;好在git提供了保存密码的功能。 在本地工程文件夹下&#xff0c;.git目录&#xff0c;保存以下配置。 [credential] helper store或者 在git bash命令行&#xff0c;执行命令 git config credential.helper store如…...

数字乡村包括哪些方面?数字乡村应用介绍

数字乡村是指利用物联网、数字化和智能化技术&#xff0c;借助现代数字智能产品、高效信息服务和物联网基础设施&#xff0c;以提高农村居民生活质量&#xff0c;助力拓展经济发展前景。 创建数字村庄有助于缩小城乡社区之间的差距&#xff0c;保障每个人都能平等地享受科技发展…...

弹性资源组件elastic-resource设计(一)-架构

简介 弹性资源组件提供动态资源能力,是分布式系统关键基础设施,分布式datax,分布式索引,事件引擎都需要集群和资源的弹性资源能力,提高伸缩性和作业处理能力。 本文介绍弹性资源组件的设计,包括架构设计和详细设计,指导开发人员代码开发 关键词 作业管理器/资源管理器/…...

C/C++笔试面试真题

C/C++笔试面试真题 1、堆和栈的区别 1、栈由系统自动分配,而堆是人为申请开辟; 2、栈获得的空间较小,而堆获得的空间较大; 3、栈由系统自动分配,速度较快,而堆一般速度比较慢; 4、栈是连续的空间,而堆是不连续的空间。 2、什么是野指针?产生的的原因? 野指针的指向的…...

【Vue3】兄弟组件传参

1. 借助父组件传参 A 组件派发一个事件&#xff0c;修改 flag 的值&#xff0c;先传递给父组件&#xff0c;然后由父组件传递给 B 组件。 缺点&#xff1a;必须由 App.vue 处理中间逻辑。 A.vue <template><div class"A"><h1>A组件</h1>…...

【CSS 中 link 和@import 的区别】

<link> 和 import 都可以用于引入 CSS 文件&#xff0c;但是两者有以下区别&#xff1a; 加载时间&#xff1a;<link> 标签在页面加载时同时加载&#xff0c;而 import 是在页面加载后才开始加载。 兼容性&#xff1a;<link> 标签可以被所有的浏览器正确解释…...

笔记二:odoo搜索、筛选和分组

一、搜索 1、xml代码 <!--搜索和筛选--><record id"view_search_book_message" model"ir.ui.view"><field name"name">book_message</field><field name"model">book_message</field><field…...

Ubuntu Zookeeper开机自启动服务

1、创建service文件 在/lib/systemd/system目录下创建zookeeper.service文件 [Unit] DescriptionApache Zookeeper server Documentationhttp://zookeeper.apache.org Requiresnetwork.target remote-fs.target Afternetwork.target remote-fs.target[Service] Typesimple Env…...

关于Matlab与Python中日期转时间戳不一致的问题

由于 Matlab 中的日期序列号精确到秒&#xff0c;而 Python 的时间戳精确到秒&#xff0c;因此在进行转换时可能会存在精度损失&#xff0c;导致转换结果不完全相同。 将 Python 中的时间戳转换为 Matlab 中的日期序列号&#xff0c;可以使用下方代码进行转换&#xff1a; de…...

【Django 笔记】第一个demo

1. pip 安装 2. django 指令 D:\software\python3\anconda3\Lib\site-packages\django\bin>django-adminType django-admin help <subcommand> for help on a specific subcommand.Available subcommands:[django]checkcompilemessagescreatecachetabledbshelldiff…...

算法通过村第十一关-位运算|白银笔记|高频题目

文章目录 前言1. 位移的妙用1.1 位1的个数1.2 比特位计算1.3 颠倒无符号整数 2. 位实现加减乘除专题2.1 位运算实现加法2.2 递归乘法 总结 前言 提示&#xff1a;他不是不想多明白些&#xff0c;但是每每在该用脑子的时候&#xff0c;他用了感情。 --老舍《黑白李》 与位运算和…...

04、EL和JSTL核心技术

目录 1 EL表达式&#xff08;熟悉&#xff09; 1.1 基本概念 1.2 主要功能 1.3 访问内置对象的数据 1.3.1访问方式 1.3.2 执行流程 1.4 访问请求参数的数据 1.5 访问Bean对象的属性 1.5.1 访问方式 1.5.2 主要区别 1.6 访问集合中的数据 1.7 常用的内置对象 …...

【LeetCode热题100】--148.排序链表

148.排序链表 对链表进行排序最适合的算法就是归并排序&#xff1a; 对链表自顶向下归并排序的过程&#xff1a; 找到链表的中点&#xff0c;以中点为分界&#xff0c;将链表拆分成两个子链表&#xff0c;寻找链表的中点可以使用快慢指针的做法&#xff0c;快指针每次移动 2步…...

分布式并行训练(DP、DDP、DeepSpeed)

[pytorch distributed] 01 nn.DataParallel 数据并行初步 数据并行 vs. 模型并行 数据并行&#xff1a;模型拷贝&#xff08;per device&#xff09;&#xff0c;数据 split/chunk&#xff08;对batch切分&#xff09; 每个device上都拷贝一份完整模型&#xff0c;每个device分…...

wan2.1-vae开源可部署:支持国产操作系统(麒麟/UOS)的适配方案

wan2.1-vae开源可部署&#xff1a;支持国产操作系统&#xff08;麒麟/UOS&#xff09;的适配方案 1. 平台介绍 muse/wan2.1-vae 文生图是基于 Qwen-Image-2512 模型的AI图像生成平台&#xff0c;支持中英文提示词&#xff0c;可生成高质量、高分辨率的图像。该平台特别针对国…...

Verilog实战精要:从语法基础到高效状态机设计

1. Verilog语法基础&#xff1a;从硬件思维出发 第一次接触Verilog时&#xff0c;很多人会把它当成普通编程语言来学&#xff0c;结果发现处处碰壁。我当年在FPGA项目上栽的第一个跟头&#xff0c;就是把阻塞赋值用在了时钟触发的always块里&#xff0c;导致仿真结果和实际硬件…...

从CMSIS-DAP到JTAG:一篇讲透Keil5/Keil4下ARM芯片的下载与调试设置差异

从CMSIS-DAP到JTAG&#xff1a;深度解析Keil环境下ARM芯片调试接口的实战差异 当你在Keil环境中从STM32F103切换到STM32F407时&#xff0c;是否遇到过下载算法突然失效的情况&#xff1f;或是更换了J-Link仿真器后&#xff0c;原本流畅的调试过程变得寸步难行&#xff1f;这些问…...

告别“替身攻击”:手把手教你用零阶优化(ZOO)直接黑盒攻击DNN模型

零阶优化实战&#xff1a;无需替代模型的黑盒对抗攻击指南 当面对一个部署在云端的深度学习API时&#xff0c;传统白盒攻击手段往往束手无策——既无法获取模型架构&#xff0c;也不能执行反向传播。本文将揭示如何运用零阶优化技术&#xff0c;仅通过输入输出查询就能构造高效…...

OliveTin高级功能指南:定时任务、文件监控和实体动态更新

OliveTin高级功能指南&#xff1a;定时任务、文件监控和实体动态更新 【免费下载链接】OliveTin OliveTin gives safe and simple access to predefined shell commands from a web interface. 项目地址: https://gitcode.com/gh_mirrors/ol/OliveTin OliveTin是一个强…...

Qwen3.5-4B-Claude-Opus真实作品:网络协议TCP三次握手状态机推理生成

Qwen3.5-4B-Claude-Opus真实作品&#xff1a;网络协议TCP三次握手状态机推理生成 1. 模型介绍 Qwen3.5-4B-Claude-4.6-Opus-Reasoning-Distilled-GGUF 是一个基于 Qwen3.5-4B 的推理蒸馏模型&#xff0c;专门针对结构化分析、分步骤回答、代码与逻辑类问题进行了优化。该模型…...

从0到1:Java+AI入门实战,看完直接上手项目

文章目录前言环境准备&#xff1a;别急着装Python&#xff0c;先把JDK升到21第一滴血&#xff1a;让Java程序说出"人话"进阶玩法&#xff1a;给AI装上"记忆"和"工具"让AI记住你们聊过啥让AI能查数据库、调接口实战项目&#xff1a;搭建私有知识库…...

夜间自动化利器:OpenClaw+nanobot定时执行爬虫任务

夜间自动化利器&#xff1a;OpenClawnanobot定时执行爬虫任务 1. 为什么选择OpenClaw做夜间自动化 凌晨三点&#xff0c;我的电脑屏幕突然亮了起来。这不是灵异事件&#xff0c;而是OpenClaw正在执行我预设的爬虫任务——收集行业数据、清洗整理、存入数据库&#xff0c;整个…...

手把手教你用STM32F405和SD卡,在阿里云物联网平台上实现OTA升级(MQTT协议详解)

STM32F405实战&#xff1a;基于SD卡与阿里云物联网平台的OTA升级全流程解析 当嵌入式设备部署在野外或工业现场时&#xff0c;固件升级往往成为工程师的噩梦。传统方式需要技术人员携带烧录器奔赴现场&#xff0c;不仅效率低下&#xff0c;在设备数量庞大或分布广泛时更是不切实…...

Hunyuan-HY-MT1.8B性能报告解读:380ms处理500token实测

Hunyuan-HY-MT1.8B性能报告解读&#xff1a;380ms处理500token实测 1. 测试背景与模型简介 腾讯混元团队最新发布的HY-MT1.5-1.8B翻译模型&#xff0c;以其轻量级架构和卓越性能引起了广泛关注。这个仅有18亿参数的模型&#xff0c;在保持高质量翻译效果的同时&#xff0c;实…...