力扣(LeetCode)1626. 无矛盾的最佳球队(C++)

news/2024/3/29 9:41:04/文章来源:https://blog.csdn.net/Innocence02/article/details/129710094

排序 + 动态规划

两个性质: ①得分最高 ② 年龄大的,分数要高。
这提示我们按照分数,或者年龄,对列表排序。先固定一个性质,才考虑另外的性质。

按照分数和年龄排序都可以。这里按照年龄,从大到小排序。年龄大的,自然在前;年龄相同,分数大的在前。在排序后的数组里,找到最大下降子序列和,满足一个条件 —— 越靠前,分数越大。即为所求。

状态定义: f[i]f[i]f[i] 表示所有以 p[i]p[i]p[i] 结尾的最大下降子序列和。
状态转移方程: f[i]=max(f[j])+p[i],j∈[0,i)f[i] = max(f[j]) +p[i], \ j \isin [0,i)f[i]=max(f[j])+p[i], j[0,i)

最后,答案序列不一定以数组末尾结尾,可能在任何位置结尾,需要维护最大的 f[i]f[i]f[i] ,即为答案。

class Solution {
public:static bool cmp(pair<int, int> x, pair<int, int> y) {return (x > y);}int bestTeamScore(vector<int>& scores, vector<int>& ages) {int n = scores.size();vector<pair<int, int>> p(n);for (int i = 0; i < n; i ++) p[i] = {ages[i], scores[i]};sort(p.begin(), p.end(), cmp);vector<int> f(n);int ans = 0;for (int i = 0; i < n ; i ++) {for (int j = i - 1; j >= 0; j --) {if (p[j].second >= p[i].second) {f[i] = max(f[i], f[j]);}}f[i] += p[i].second;ans = max (ans, f[i]);}return ans;}
};
  1. 时间复杂度 : O(n2)O(n ^ 2)O(n2)nnn 是球员的数目,一共 nnn 状态,平均每个状态转移 nnn 次,时间复杂度 O(n2)O(n^2)O(n2)
  2. 空间复杂度 : O(n)O(n)O(n) ,状态数组和分数-年龄数组的空间复杂度 O(n)O(n)O(n)

AC

AC

致语

  • 理解思路很重要
  • 读者有问题请留言,清墨看到就会回复的。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_274584.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

串口通信(STM32演示实现)

目录 一、串行通信的概念 二、寄存器 2.1控制寄存器USART_CR1 2.2控制寄存器USART_CR2​编辑 2.3串口寄存器USART_BRR 2.4 USART_ISR 2.5USART_TDR 2.6USART_RDR​编辑 三、实现串口数据的收发 一、串行通信的概念 u通信&#xff0c;最少要有两个对象&#xff0c;一个收…

提高曝光率:外贸网站如何充分利用谷歌优化赢得客户

自从我从事外贸行业以来&#xff0c;谷歌优化一直是我关注的重点。 作为一个外贸从业者&#xff0c;我深知提高网站在谷歌搜索引擎中的排名对企业的重要性。 那么&#xff0c;如何利用谷歌优化来提高外贸网站的曝光率&#xff0c;从而赢得更多客户呢&#xff1f; 以下是我在…

I2C和SPI总线以及通信

通讯属性 概括 Serial/parallel 串行/并行Synchronous/asynchronous 同步/异步Point-to-point / bus 点对点 总线Half-duplex/full-duplex 半双工/全双工Master-slave/ equal partners 主从/对等single-ending / differential 单端/差分 点对点和总线 点对点通讯 只有两个通…

【UE】使用初学者内容包创建简单的地形材质

效果步骤新建一个材质打开该材质&#xff0c;创建一个“layerblend”节点创建3个数组元素设置图层命名、混合类型和预览权重使用初学者内容包中的“T_Rock_Basalt_D”纹理、“T_Ground_Gravel_D”纹理和“T_Ground_Grass_D”纹理使用“Terrain_Mat”材质创建一个地形可以用雕刻…

PMP项目管理证书的含金量高吗?

PMP 项目管理证书的含金量一直是大家非常关心的一个问题&#xff0c;其实没必要纠结含金量&#xff0c;想从事项目管理岗位的&#xff0c;考就对了。 先给大家上个目录&#xff0c;再来细细说明 一、PMP带来的好处&#xff08;含金量&#xff09;二、PMP适合什么人考三、PMP 考…

CCS v6 导入工程调试仿真烧写程序教程

点击CCS图标&#xff0c;选择要放置的workplace 1.然后配置仿真器参数&#xff1a;View>Target Configurations 然后开始配置仿真器参数&#xff0c;大家可以根据自己的器件&#xff1a; 选择好之后&#xff0c;点击save 2.导入新的工程 然后就可以看到工程已经导入成功了&a…

掌握CentOS7环境下的Docker使用(八)阿里云镜像仓库实战、harbor仓库搭建与实战、本地镜像容器的载入载出

文章目录镜像仓库简介公共镜像仓库私有镜像仓库阿里云镜像仓库的搭建与使用创建仓库登录将镜像推送到Registry从Registry中拉取镜像harbor仓库搭建与使用搭建harbor仓库配置与使用harbor仓库本地镜像容器的载入与载出保存镜像保存容器可能出现的问题输入正确的密码登录不进去阿…

人员玩手机离岗识别检测系统 yolov5

人员玩手机离岗识别检测系统根通过pythonyolov5网络模型识别算法技术&#xff0c;人员玩手机离岗识别检测算法可以对画面中人员睡岗离岗、玩手机打电话、脱岗睡岗情况进行全天候不间断进行识别检测报警提醒。Python是一种由Guido van Rossum开发的通用编程语言&#xff0c;它很…

Spring核心概念

Spring核心概念1 介绍1.1 为什么要学?1.2 学什么?1.3 怎么学?2 Spring相关概念2.1 初识Spring2.1.1 Spring家族2.1.2 了解Spring发展史2.2 Spring系统架构2.2.1 系统架构图2.2.2 课程学习路线2.3 Spring核心概念2.3.1 目前项目中的问题2.3.2 IOC、IOC容器、Bean、DI2.3.3 核…

Open Inventor 2023.1RC 将更大变化

体积可视化 具有单一分辨率的体积渲染 使用单一分辨率渲染卷更容易&#xff0c;因为卷可视化现在可以根据当前设置和硬件配置自动计算出最佳分辨率。使用单一分辨率可防止在默认模式下可能可见的不良伪影。 下图突出显示了单一分辨率的优势。在左图中&#xff0c;在 2 种分辨…

深度学习:GPT1、GPT2

深度学习&#xff1a;GPT1、GPT2、GPT3的原理与模型代码解读GPT-1IntroductionFramework自监督学习微调ExperimentGPT-2IntroductionApproachConclusionGPT-3GPT-1 Introduction GPT-1&#xff08;Generative Pre-training Transformer-1&#xff09;是由OpenAI于2018年发布的…

Python读取,预处理DICOM文件方式

需要的库 ●Simpleitk 安装命令&#xff1a; conda install -c simpleitk simpleitk使用&#xff1a; import SimpleITK as sitk●pydicom&#xff08;不推荐&#xff0c;可能有些文件打不开&#xff09; 安装命令&#xff1a; conda install -c conda-forge pydicom●PIL …

linux系统添加审计用户并进行权限控制

审计账号只用于审计功能&#xff0c;其权限可在普通账号基础上进行修改.创建审计用户 sjyhuseradd sjyh为审计用户设置登录密码passwd sjyh会有如下提示&#xff0c;按照提示依次修改即可:更改用户 sjyh 的密码 。 新的 密码&#xff1a; 重新输入新的 密码&#xff1a; 重新输…

平庸的恐惧,就业的烦恼——致互联网人进退两难的35岁

最近阿道看到了一些黑色幽默的新闻。 事情是这样的&#xff0c;某媒体发文抨击职场的“35岁”歧视&#xff0c;但后来被扒出&#xff0c;该媒体所属的机构在发布招聘信息时&#xff0c;却明确地标注了受聘者的年龄界限。 这一通操作属实把大家看傻了&#xff0c;后来阿道又在…

AVL树大讲堂

1.基础概念介绍 首先在前面我们介绍了二叉搜索树&#xff0c;但是如果当存储的数据接近有序或者恰巧有序的时候&#xff0c;二叉搜索树将逐渐退化为单支树&#xff0c;导致搜索效率降低&#xff0c;因此我们的avl树便为了解决这一问题而诞生了。 基础性质&#xff1a;当向二叉…

Tone Mapping中luma滤波(降噪)对噪声放大的定性分析

Tone Mapping中luma滤波对噪声放大的定性分析 在tone mapping过程中&#xff0c;通常经过统计之后得到一条mapping曲线&#xff0c;记这条曲线为f(x)f(x)f(x)&#xff0c;mapping过程中&#xff0c;对于给定的点&#xff0c;假定其亮度为xxx&#xff0c;映射后为f(x)f(x)f(x)&…

虚拟机设置桥接模式:静态IP

一、下载virtual box并安装系统 链接&#xff1a;https://www.virtualbox.org/ 安装并配置Ubuntu桌面版&#xff1a;https://blog.csdn.net/Zhichao_Zhang/article/details/127142410?spm1001.2014.3001.5506 安装并配置CentOS7&#xff1a;https://blog.csdn.net/csp7321711…

【学习笔记】《Writing Science》14-21

文章目录14 Energizing Writing 充满活力的写作14.1. ACTIVE VERSUS PASSIVE VOICE 主动语态和被动语态14.1.1. Controlling Perspective 控制视角14.1.2. Hiding the Actor 隐藏演员14.2. FUZZY VERBS 模糊动词14.2.1. Fuzzy Hypotheses 模糊假设14.3. NOMINALIZATIONS 名词化…

自动化测试学习(七)-正则表达式,你真的会用吗?

目录 一、正则表达式在python中如何使用 二、用正则表达式匹配更多模式 三、常用字符分类的缩写代码 总结 所谓正则表达式&#xff08;regex&#xff09;&#xff0c;就是一种模式匹配&#xff0c;学会用正则匹配&#xff0c;就可以达到事半功倍的效果。 一、正则表达式在…

本地资源检测|单规则多阈值设置功能上线

作为一款可以全面自动检测项目静态工程内各项资源、代码和设置的UWA服务&#xff0c;本地资源检测能够帮助项目组制定合理的资源与代码标准&#xff0c;及时发现潜在的性能问题和异常错误&#xff0c;建立有效的开发规范意识。 此次3.1.0版本更新&#xff0c;在优化和完善现有…