当前位置: 首页 > 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分…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

华为OD机试-食堂供餐-二分法

import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

【Java学习笔记】BigInteger 和 BigDecimal 类

BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点&#xff1a;传参类型必须是类对象 一、BigInteger 1. 作用&#xff1a;适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

【Go语言基础【12】】指针:声明、取地址、解引用

文章目录 零、概述&#xff1a;指针 vs. 引用&#xff08;类比其他语言&#xff09;一、指针基础概念二、指针声明与初始化三、指针操作符1. &&#xff1a;取地址&#xff08;拿到内存地址&#xff09;2. *&#xff1a;解引用&#xff08;拿到值&#xff09; 四、空指针&am…...

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要&#xff1a; 近期&#xff0c;在使用较新版本的OpenSSH客户端连接老旧SSH服务器时&#xff0c;会遇到 "no matching key exchange method found"​, "n…...

2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)

安全领域各种资源&#xff0c;学习文档&#xff0c;以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具&#xff0c;欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...