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

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

Python实现prophet 理论及参数优化

文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

用docker来安装部署freeswitch记录

今天刚才测试一个callcenter的项目&#xff0c;所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...