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+i∗a[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
题面 分析: 题目最终需要达到MEX位0,也就是从最开始的MEX变成0后m的最小值,可以设 d p i dp_i dpi表示当前MEX为 i i i时,m的最小值,那么就可以根据前一个状态推出后一个状态,也就是假如当前MEX是 i i …...
奥斯卡·王尔德
奥斯卡王尔德 奥斯卡王尔德(Oscar Wilde,1854年10月16日—1900年11月30日),出生于爱尔兰都柏林,19世纪英国(准确来讲是爱尔兰,但是当时由英国统治)最伟大的作家与艺术家之一…...
IDEA常用快捷键大全
整理了一些IDEA开发常用的快捷键: 快捷键组合实现效果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之多线程的综合练习二
练习六:多线程统计并求最大值 需求: 在上一题基础上继续完成如下需求: 每次抽的过程中,不打印,抽完时一次性打印(随机) 在此次抽奖过程中,抽奖箱1总共产生了6个奖项。 分别为:10,20,100,50…...
selenium下载安装 -- 使用谷歌驱动碰到的问题
安装教程参考: http://c.biancheng.net/python_spider/selenium.html 1. 谷歌浏览器和谷歌驱动版本要对应(但是最新版本谷歌对应的驱动是没有的,因此要下载谷歌历史其他版本): 谷歌浏览器历史版本下载: https://www.chromedownloads.net/chrome64win/谷歌浏览器驱动下载: http:…...
开放式耳机怎么选择、300之内最好的耳机推荐
开放式耳机凭借不入耳、不伤耳、安全更舒适的佩戴体验,得到了越来越多音乐爱好者和专业人士的青睐。开放式耳机不需要插入耳道,在佩戴时可以更加自然和轻松,减少了长时间佩戴引起的不适感,而且不会完全隔绝外界声音,用…...
git密码提交切换SSH提交
git保存密码 每次登录都要输入密码是显示繁琐,好在git提供了保存密码的功能。 在本地工程文件夹下,.git目录,保存以下配置。 [credential] helper store或者 在git bash命令行,执行命令 git config credential.helper store如…...
数字乡村包括哪些方面?数字乡村应用介绍
数字乡村是指利用物联网、数字化和智能化技术,借助现代数字智能产品、高效信息服务和物联网基础设施,以提高农村居民生活质量,助力拓展经济发展前景。 创建数字村庄有助于缩小城乡社区之间的差距,保障每个人都能平等地享受科技发展…...
弹性资源组件elastic-resource设计(一)-架构
简介 弹性资源组件提供动态资源能力,是分布式系统关键基础设施,分布式datax,分布式索引,事件引擎都需要集群和资源的弹性资源能力,提高伸缩性和作业处理能力。 本文介绍弹性资源组件的设计,包括架构设计和详细设计,指导开发人员代码开发 关键词 作业管理器/资源管理器/…...
C/C++笔试面试真题
C/C++笔试面试真题 1、堆和栈的区别 1、栈由系统自动分配,而堆是人为申请开辟; 2、栈获得的空间较小,而堆获得的空间较大; 3、栈由系统自动分配,速度较快,而堆一般速度比较慢; 4、栈是连续的空间,而堆是不连续的空间。 2、什么是野指针?产生的的原因? 野指针的指向的…...
【Vue3】兄弟组件传参
1. 借助父组件传参 A 组件派发一个事件,修改 flag 的值,先传递给父组件,然后由父组件传递给 B 组件。 缺点:必须由 App.vue 处理中间逻辑。 A.vue <template><div class"A"><h1>A组件</h1>…...
【CSS 中 link 和@import 的区别】
<link> 和 import 都可以用于引入 CSS 文件,但是两者有以下区别: 加载时间:<link> 标签在页面加载时同时加载,而 import 是在页面加载后才开始加载。 兼容性:<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 中的日期序列号精确到秒,而 Python 的时间戳精确到秒,因此在进行转换时可能会存在精度损失,导致转换结果不完全相同。 将 Python 中的时间戳转换为 Matlab 中的日期序列号,可以使用下方代码进行转换: 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 递归乘法 总结 前言 提示:他不是不想多明白些,但是每每在该用脑子的时候,他用了感情。 --老舍《黑白李》 与位运算和…...
04、EL和JSTL核心技术
目录 1 EL表达式(熟悉) 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.排序链表 对链表进行排序最适合的算法就是归并排序: 对链表自顶向下归并排序的过程: 找到链表的中点,以中点为分界,将链表拆分成两个子链表,寻找链表的中点可以使用快慢指针的做法,快指针每次移动 2步…...
分布式并行训练(DP、DDP、DeepSpeed)
[pytorch distributed] 01 nn.DataParallel 数据并行初步 数据并行 vs. 模型并行 数据并行:模型拷贝(per device),数据 split/chunk(对batch切分) 每个device上都拷贝一份完整模型,每个device分…...
智慧医疗能源事业线深度画像分析(上)
引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...
什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南
文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果,支持8kHz~96kHz采样率,集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器,适用于高保真音频采集场景。 2. 核心特性 高精度:24位分辨率,…...
sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!
简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求,并检查收到的响应。它以以下模式之一…...
视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)
前言: 最近在做行为检测相关的模型,用的是时空图卷积网络(STGCN),但原有kinetic-400数据集数据质量较低,需要进行细粒度的标注,同时粗略搜了下已有开源工具基本都集中于图像分割这块,…...
uniapp 字符包含的相关方法
在uniapp中,如果你想检查一个字符串是否包含另一个子字符串,你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的,但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...
MySQL:分区的基本使用
目录 一、什么是分区二、有什么作用三、分类四、创建分区五、删除分区 一、什么是分区 MySQL 分区(Partitioning)是一种将单张表的数据逻辑上拆分成多个物理部分的技术。这些物理部分(分区)可以独立存储、管理和优化,…...
es6+和css3新增的特性有哪些
一:ECMAScript 新特性(ES6) ES6 (2015) - 革命性更新 1,记住的方法,从一个方法里面用到了哪些技术 1,let /const块级作用域声明2,**默认参数**:函数参数可以设置默认值。3&#x…...
二维FDTD算法仿真
二维FDTD算法仿真,并带完全匹配层,输入波形为高斯波、平面波 FDTD_二维/FDTD.zip , 6075 FDTD_二维/FDTD_31.m , 1029 FDTD_二维/FDTD_32.m , 2806 FDTD_二维/FDTD_33.m , 3782 FDTD_二维/FDTD_34.m , 4182 FDTD_二维/FDTD_35.m , 4793...
