D. Jellyfish and Mex Codeforces Round 901 (Div. 2)
Problem - D - Codeforces
题目大意:有一个n个数的数组a,数m初始为0,每次操作可以删除任意一个数,然后m加上那个数,求n次操作和m的最小值
1<=n<=5000;0<=a[i]<=1e9
思路:可以发现,如果我们要删除某个数,那么一定要把所有和这个数相等的数全部删去,这样才能使MEX变小,同时,所有大于MEX的数删去的花费都是0,所以我们每次操作的数的大小都是递减的,且只会操作MEX到0。
那么我们令dp[i]等于MEX等于i时的最小花费,我们从MEX到0枚举i,同时枚举该删哪个数,也就是从0到i-1遍历,当前最小花费就是不删这个数dp[j],或者删这个数也就是dp[i]+当前MEX*(这个数数量-1)再加这个数,转移方程为dp[j]=min(dp[j],dp[i]+i*(cnt[j]-1)+j)
//#include<__msvc_all_public_headers.hpp>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e3 + 5;
ll n;
ll a[N];
ll cost[N];
ll cnt[N];
void init()
{for (int i = 0; i <= n; i++){cost[i] = 1e18;cnt[i] = 0;}
}
ll gcd(ll a, ll b)
{return b ? gcd(b, a % b) : a;
}
ll lowbit(ll x)
{return x & (-x);
}
void solve()
{ll m;cin >> n;init();for (int i = 1; i <= n; i++){cin >> a[i];if (a[i] <= n){//MEX最大为n,大于n的都可以随便删cnt[a[i]]++;}}int mex = 0;while (cnt[mex]){//找当前的MEXmex++;}cost[mex] = 0;for (ll i = mex; i >= 0; i--){for (ll j = 0; j < i; j++){cost[j] = min(cost[j], cost[i] + i * (cnt[j] - 1) + j);}}cout << cost[0] << endl;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);int t;cin >> t;while (t--){solve();}return 0;
}
相关文章:
D. Jellyfish and Mex Codeforces Round 901 (Div. 2)
Problem - D - Codeforces 题目大意:有一个n个数的数组a,数m初始为0,每次操作可以删除任意一个数,然后m加上那个数,求n次操作和m的最小值 1<n<5000;0<a[i]<1e9 思路:可以发现&am…...
操作系统内存管理相关
1. 虚拟内存 1.1 什么是虚拟内存 虚拟内存是计算机系统内存管理的一种技术,我们可以手动设置自己电脑的虚拟内存。不要单纯认为虚拟内存只是“使用硬盘空间来扩展内存“的技术。虚拟内存的重要意义是它定义了一个连续的虚拟地址空间,并且 把内存扩展到硬…...
Sui流动性质押黑客松获胜者公布,助力资产再流通
Sui流动质押黑客松于日前结束Demo Day演示,其中有五个团队获奖、六个团队荣誉提名,共有超过30个项目获得参赛资格。此外,有两个团队赢得了Sui上DeFi协议提供的赏金。 本次黑客松的目的是挖掘并奖励将流动质押功能集成到其apps和产品中的开发…...
为什么在使用PageHelper插件时,指定的每页记录数大小失效?显示所有的记录数
1.问题现象: 这里指定每页显示5条,却把所有的记录数都显示出来了 2.分析: 之前是可以的,然后发现:PageHelper.startPage(pageNum,pageSize) 和执行sql的语句 顺序颠倒了,然后就出错了。 3.验证…...
XML文档基础
什么是XML XML (eXtensible Markup Language,可扩展标记语言) 是一种用于存储和传输数据的文本文件格式。用户可以按照XML规则自定义标记,XML 的设计目标是传输数据,而不是显示数据,因此它是一种通用的标记语言,可用于…...
软考知识汇总-软件工程
软件工程 1 能力成熟度模型(CMM)2 能力成熟度模型集成(CMMI)2.1阶段式模型2.2 连续式模型 3 软件过程模型 1 能力成熟度模型(CMM) 将软件工程成熟度分为5个级别 初始级:杂乱无章,很…...
力扣:119. 杨辉三角 II(Python3)
题目: 给定一个非负索引 rowIndex,返回「杨辉三角」的第 rowIndex 行。 在「杨辉三角」中,每个数是它左上方和右上方的数的和。 来源:力扣(LeetCode) 链接:力扣(LeetCode)…...
指针笔试题(带解析版)
题目2: struct MyStruct {int num;char* pcname;short sdate;char cha[2];short sba[4]; }*p; //结构体大小为32字节 //p0x100000 int main() {p 0x100000;printf("%p\n", p 0x1);//p:结构体指针,1下一个结构体指针,…...
服务器搭建(TCP套接字)-libevent版(服务端)
Libevent 是一个开源的事件驱动库,用于开发高性能、并发的网络应用程序。它提供了跨平台的事件处理和网络编程功能,具有高性能、可扩展性和可移植性。下面详细讲解 Libevent 的主要组成部分和使用方法。 一、事件基础结构(event_base&#x…...
斐波那契模型系列【动态规划】
动态规划步骤 1、状态表示 是什么:dp表(可能是一维或二维数组)里的值所表示的含义。 怎么来: 1、题目要求 2、经验题目要求 3、发现重复子问题 2、状态转移方程 dp[i]... 3、初始化 保证填表不越界 4、填表顺序 5、返回值 写代码时…...
【Java】微服务——Nacos注册中心
目录 1.Nacos快速入门1.1.服务注册到nacos1)引入依赖2)配置nacos地址3)重启 2.服务分级存储模型2.1.给user-service配置集群2.2.同集群优先的负载均衡 3.权重配置4.环境隔离4.1.创建namespace4.2.给微服务配置namespace 5.Nacos与Eureka的区别…...
Redis Cluster Gossip Protocol: PING, PONG, MEET
返回目录 PING / PONG / MEET 的发送 过程 计算freshNodes。freshNodes表示在消息中能携带的,在cluster节点字典中的节点总数,但需要减去myself和对端节点,因为myself的信息会存储在消息头中。实际上,并非所有在cluster节点字典…...
httpserver 下载服务器demo 以及libevent版本的 httpserver
实现效果如下: 图片可以直接显示 cpp h 这些可以直接显示 其他的 则是提示是否要下载 单线程 还有bug 代码如下 先放上来 #include "httpserver.h" #include "stdio.h" #include <stdlib.h> #include <arpa/inet.h> #include…...
构建强大的RESTful API:@RestController与@Controller的对比与应用
构建强大的RESTful API:RestController与Controller的对比与应用 前言什么是RESTful APIRestController,Controller,ResponseBody1. Controller注解:2. RestController注解:3. ResponseBody注解: 示例非thy…...
【Java-LangChain:使用 ChatGPT API 搭建系统-10】评估(下)-当不存在一个简单的正确答案时
第十章,评估(下)-当不存在一个简单的正确答案时 在上一章中,了解了如何评估 LLM 模型在 有明确正确答案 的情况下的输出,我们可以编写一个函数来判断 LLM 输出是否正确地分类并列出产品。 然而,如果 LLM …...
【微服务的集成测试】python实现-附ChatGPT解析
1.题目 微服务的集成测试 知识点:深搜 时间限制: 1s 空间限制: 256MB 限定语言:不限 题目描述: 现在有n个容器服务,服务的启动可能有一定的依赖性 (有些服务启动没有依赖)其次服务自身启动加载会消耗一些时间。 给你一个 nxn 的二维矩阵 useTime,其中 useTime[i][i]=10 表示…...
Mesa新版来袭
Mesa 17.1.6 发布了,Mesa 是一个三维(3D)图形库的开源集合,其主要目标是在 Linux / UNIX 操作系统下实现各种 API(应用程序编程接口)和 OpenGL 规范。 它面向 3D 计算机图形,硬件加速 3D 渲染和…...
基于 SpringBoot 2.7.x 使用最新的 Elasticsearch Java API Client 之 ElasticsearchClient
1. 从 RestHighLevelClient 到 ElasticsearchClient 从 Java Rest Client 7.15.0 版本开始,Elasticsearch 官方决定将 RestHighLevelClient 标记为废弃的,并推荐使用新的 Java API Client,即 ElasticsearchClient. 为什么要将 RestHighLevelC…...
辅助驾驶功能开发-功能对标篇(15)-NOA领航辅助系统-吉利
1.横向对标参数 厂商吉利车型FX11/EX11/DCY11/G636上市时间2022Q4方案6V5R+1DMS摄像头前视摄像头1*(8M)侧视摄像头/后视摄像头1环视摄像头4DMS摄像头1雷达毫米波雷达54D毫米波雷达/超声波雷达12激光雷达/域控供应商福瑞泰克辅助驾驶软件供应商福瑞泰克高精度地图百度芯片TDA4 T…...
javascript: Sorting Algorithms
// Sorting Algorithms int JavaScript https://www.geeksforgeeks.org/sorting-algorithms/ /** * file Sort.js * 1. Bubble Sort冒泡排序法 * param arry * param nszie */ function BubbleSort(arry, nszie) {var i, j, temp;var swapped;for (i 0; i < nszie - 1; i)…...
从JLink驱动安装失败,聊聊老旧Win7系统下嵌入式工具链的“版本锁定”现象
从JLink驱动安装失败看嵌入式工具链的版本锁定困境 当你在Windows 7系统上尝试安装最新版JLink驱动时,那个顽固的黄色感叹号是否曾让你抓狂?这看似简单的驱动问题背后,隐藏着一个困扰嵌入式开发领域多年的系统性难题——工具链的版本锁定现象…...
Linux服务器运维实战:为什么我更推荐用apt安装FileZilla而不是下载tar包?
Linux服务器运维实战:为什么我更推荐用apt安装FileZilla而不是下载tar包? 每次在Linux服务器上部署FTP客户端时,我都会面临一个选择:是直接apt install filezilla,还是去官网下载tar包手动安装?五年前我可能…...
3步搞定无损音乐自由:网易云音乐歌单批量下载终极指南
3步搞定无损音乐自由:网易云音乐歌单批量下载终极指南 【免费下载链接】NeteaseCloudMusicFlac 根据网易云音乐的歌单, 下载flac无损音乐到本地.。 项目地址: https://gitcode.com/gh_mirrors/nete/NeteaseCloudMusicFlac 你是否曾经想过,只需一个…...
终极指南:掌握虚幻引擎资源逆向工程与UAssetGUI实战应用
终极指南:掌握虚幻引擎资源逆向工程与UAssetGUI实战应用 【免费下载链接】UAssetGUI A tool designed for low-level examination and modification of Unreal Engine game assets by hand. 项目地址: https://gitcode.com/gh_mirrors/ua/UAssetGUI 在游戏开…...
Skill Library:AI智能体技能库的模块化设计与工程实践
1. 项目概述:一个为AI智能体打造的“技能武器库”如果你和我一样,每天都在和Claude、ChatGPT、Cursor这些AI工具打交道,那你肯定也经历过这样的时刻:想让AI帮你写个复杂的SQL查询、设计一个微服务架构,或者起草一份产品…...
Dell G15终极散热控制指南:开源温度管理软件全面解析
Dell G15终极散热控制指南:开源温度管理软件全面解析 【免费下载链接】tcc-g15 Thermal Control Center for Dell G15 - open source alternative to AWCC 项目地址: https://gitcode.com/gh_mirrors/tc/tcc-g15 还在为Dell G15笔记本过热问题而烦恼吗&#…...
Lua RTOS在ESP32上的应用:从架构解析到物联网项目实战
1. 项目概述:当Lua遇上RTOS,为ESP32注入灵魂 如果你玩过ESP32,大概率用过Arduino框架或者乐鑫官方的ESP-IDF。前者简单易上手,但深度定制和实时性有限;后者功能强大专业,但C语言开发门槛不低,调…...
C语言核心知识体系总结
C语言核心知识体系总结本文旨在系统梳理C语言的基础与进阶知识点,帮助读者建立清晰的知识框架。内容涵盖:程序编译过程、数据类型与变量、运算符与表达式、控制结构、函数、指针、结构体与共用体、动态内存分配、文件操作等。适合复习巩固或查漏补缺。第…...
Windows系统mfc140.dll文件丢失无法启动程序解决
在使用电脑系统时经常会出现丢失找不到某些文件的情况,由于很多常用软件都是采用 Microsoft Visual Studio 编写的,所以这类软件的运行需要依赖微软Visual C运行库,比如像 QQ、迅雷、Adobe 软件等等,如果没有安装VC运行库或者安装…...
技能图谱探索器:从数据建模到交互可视化的全栈实现
1. 项目概述:一个技能图谱的探索工具最近在GitHub上看到一个挺有意思的项目,叫nitzzzu/openclaw-skills-explorer。光看名字,openclaw和skills-explorer这两个词就挺有画面感的。我第一反应是,这应该是一个用来探索、梳理或可视化…...
