2023-08-01力扣今日二题-Hard-DPLIS优先队列-好题
链接:
354. 俄罗斯套娃信封问题
题意:
一个信封有长宽,如果一个信封的长宽均严格大于另一个信封,那么大的这个信封可以装下小的这个信封
求最多能套娃几个信封
解:
类似普通的最长上升子序列,但是信封有两个数据,第一时间想到的是优先队列排序,但是我们发现这两个数据并没有优先级,也不能通过加减乘除之类的操作制造一个新的关键数据
我们看一下正常最长上升子序列的解法动态规划的LIS算法,它的DP[i-1](下标初始为0,使用后置++的方法赋值和保存长度)表示长度i的上升子序列最后一位的最小值。
主要过程我将他分为两步:更新&扩展,更新是指我的数值并不足以扩展出更长的上升子序列,但是我可以使某个长度的上升子序列最后一位更小(结尾越小理论越长);扩展则是指我的数值可以完成扩展,那我就增加DP计数并保存这个数值。
那假如我们用w升序,h在此基础上升序,那么对于w来说,后进的永远大于等于先进的,这是部分符合的,所以如果我们遇到w5h15,w10h10,w15h20,完全可以用w10h10更新w5h15(w10也能满足w15,优先选择h最小的);但是如果存在同w下h的升序,例如w5h15,w10h10,w10h20,我们就能发现更新完以后,w10h20并不能接在w10h10后面,反而应该接在w5h15后面。
我们分析这个错误就可以发现,如果w升序排序,我们就可以用大的w小的h更新原先小的w大的h,如果同w情况下h升序排序,更新会先进行,先更新的后果/错误就是如果被更新的是目前求出来的最长子序列最后一位的最小值,那么本来能扩展长度的数据就会因为这个更新后的w和自身相同无法完成扩展,或者更新后的h小于原先的h进行错误扩展(看你怎么判断扩展的=-=)(当然也会导致其他更新的错误)
先更新后扩展不行,能不能先扩展后更新,实际上这就是答案:让w升序的情况下h降序,这样同w的情况下大的h就会先进行处理。
在处理一组新的w之前,我们已知数组里的old-w都小于这个new-w,那么如果new-w的h大于最后一位,就可以进行扩展,然后再遍历new-w中h降序的其他数据,来更新DP数组;我们能确保更新并不会导致已经求出的最长子序列长度变短,同时数组里只包含new-w和小于new-w的old-w;在条件w1>=w2&&h1<h2下,我们可知用w1h1更新w2h2将会是合法的。
实际代码:
#include<bits/stdc++.h>
using namespace std;
struct cmp
{bool operator() (const pair<int,int> &A,const pair<int,int> &B){if(A.first==B.first) return A.second<B.second;else return A.first>B.first;}
};
int maxEnvelopes(vector<vector<int>>& envelopes)
{int lg=envelopes.size(),now=0;vector<int>dp(lg); priority_queue<pair<int,int>,vector<pair<int,int>>,cmp>pq;for(const auto &envelope:envelopes) pq.push({envelope[0],envelope[1]});while(!pq.empty()){pair<int,int>temp=pq.top();pq.pop();if(now==0) dp[now++]=temp.second;else{if(temp.second>dp[now-1]) dp[now++]=temp.second;else{auto upper=lower_bound(dp.begin(),dp.begin()+now,temp.second);if(upper==dp.begin()+now||upper==dp.end()) continue;//没找到*upper=min(*upper,temp.second);}}}return now;
}
int main()
{vector<vector<int>> envelopes;int n;cin>>n;for(int i=0;i<n;i++){int a,b;cin>>a>>b;envelopes.push_back({a,b}); }int ans=maxEnvelopes(envelopes);cout<<ans<<endl;return 0;
}
限制:
1 <= envelopes.length <= 105envelopes[i].length == 21 <= wi, hi <= 105
相关文章:
2023-08-01力扣今日二题-Hard-DPLIS优先队列-好题
链接: 354. 俄罗斯套娃信封问题 题意: 一个信封有长宽,如果一个信封的长宽均严格大于另一个信封,那么大的这个信封可以装下小的这个信封 求最多能套娃几个信封 解: 类似普通的最长上升子序列,但是信封…...
并发 如何创建线程 多线程
进程:一个程序的执行过程 线程:一个方法就是一个线程 并发:多个线程抢夺一个资源 操作同一个对象 创建线程方法1 //创建线程方法1 继承Thread类 重写润方法 调用start开启线程 public class TestThead extends Thread{Overridepublic voi…...
亚马逊鲲鹏系统是怎么引流的?
亚马逊鲲鹏系统有三种引流方式,可设置通过亚马逊站点搜索、站外引流、直接访问产品页面进入到相关产品页面进行操作。 1、通过亚马逊站点搜索 正常的登录到我们的亚马逊主页,然后通过设置关键词及asin,最后进入你指定的产品,进行…...
第五章 Git
5-1、Git的安装 1、为什么要使用代码版本控制系统 【1】版本控制 【2】开发中存在的麻烦 2、Git和SVN的对比 【1】Git和SVN对比 (1)SVN (2)Git 3、Git下载和安装 【1】下载 【2】安装 一路下一步就好了,更换安装…...
无涯教程-Lua - 变量声明
变量的名称可以由字母,数字和下划线字符组成。它必须以字母或下划线开头,由于Lua区分大小写,因此大写和小写字母是不同的。 在Lua中,尽管无涯教程没有变量数据类型,但是根据变量的范围有三种类型。 全局变量(Global) …...
vue3学习-组件基础、深入组件
组件 基本概述 单独的 .vue文件 单文件组件(SFC)(single file component) 使用子组件 导入,无需注册,直接使用编译时,区分大小写可使用 />关闭标签 传递 props 需要再组件上声明注册 def…...
原型链污染分析
原型链污染问题 原型链原型的继承原型链污染 原型链 原型的继承 先创建一个对象,查看一下属性 const obj { prop1: 111, prop2: 222,} 这里的Object.prototype就是对象的原型。 原型里面有许多的属性,这里面的constructor是我们需要着重关注的。 除此…...
RF PCB的9条改进型建议
1.小功率的RF的PCB设计中,主要使用标准的FR4材料(绝缘特性好、材质均匀、介电常数ε=4,10%)。主要使用4层~6层板,在成本非常敏感的情况下可以使用厚度在1mm以下的双面板,要保证反面是一个完整的地层,同时由于双面板的厚度在1mm以上,使得地层和信号层之间的FR4介质较厚,…...
网络安全(黑客)自学就业
前段时间,遇到网友提问,说为什么我信息安全专业的找不到工作? 造成这个结果主要是有两大方面的原因。 第一个原因,求职者本身的学习背景问题。那这些问题就包括学历、学校学到的知识是否扎实,是否具备较强的攻防实战…...
uni-app选择器( uni-data-picker)选择任意级别
背景说明 uni-app 官方的插件市场有数据驱动选择器,可以用作多级分类的场景。引入插件后,发现做不到只选择年级,不选择班级(似乎,只能到最后子节点了)。 需求中,有可能选择的不是叶子。比如&a…...
网络入侵探测器Pi.Alert
什么是 Pi.Alert ? Pi.Alert 是 WIFI/LAN 入侵探测器。通过扫描连接到您的 WIFI/LAN 的设备,提醒您未知设备的连接。它还警告断开“始终连接”的设备。 Pi.Alert 使用了三种扫描方式 方式1:arp-scan。arp扫描系统实用程序用于使用 arp 帧搜索…...
Flask项目打包为exe(附带项目资源,静态文件)
1.在项目根目录创建my_app.spec文件,内容如下: # -*- mode: python ; coding: utf-8 -*-block_cipher Nonea Analysis([server.py], # flask入口pathex[],binaries[], datas[("E:/**/templates","/templates"),("E:/**/s…...
无代码开发(BIP旗舰版-YonBuilder)
目录 我的应用 新建领域 菜单管理 应用构建 新建应用 对象建模 新增业务对象 新增业务实体 页面建模 新增页面 编辑页面 发布管理 我的应用 角色管理 yonbuilder开发平台,提供标准服务和专业开发服务; 本篇文章只演示标准服务的可视化应用…...
誉天程序员-瀑布模型-敏捷开发模型-DevOps模型比较
文章目录 2. 项目开发-开发方式2.1. 瀑布开发模型2.2. 敏捷开发模型2.3. DevOps开发模型2.4. 区别 自增主键策略1、数据库支持主键自增自增和uuid方案优缺点 2. 项目开发-开发方式 由传统的瀑布开发模型、敏捷开发模型,一跃升级到DevOps开发运维一体化开发模型。 …...
flutter:占位视图(骨架屏、shimmer)
前言 有时候打开美团,在刚加载数据时会显示一个占位视图,如下: 那么这个是如何实现的呢?我们可以使用shimmer来开发该功能 实现 官方文档 https://pub-web.flutter-io.cn/packages/shimmer 安装 flutter pub add shimmer示例…...
【雕爷学编程】MicroPython动手做(30)——物联网之Blynk 4
知识点:什么是掌控板? 掌控板是一块普及STEAM创客教育、人工智能教育、机器人编程教育的开源智能硬件。它集成ESP-32高性能双核芯片,支持WiFi和蓝牙双模通信,可作为物联网节点,实现物联网应用。同时掌控板上集成了OLED…...
python-网络爬虫.BS4
BS4 Beautiful Soup 是一个可以从HTML或XML文件中提取数据的Python库, 它能够通过你喜欢的转换器实现惯用的文档导航、查找、修改文档的方 式。 Beautiful Soup 4 官方文档:https://www.crummy.com/software/BeautifulSoup/bs4/doc.zh/ 帮助手册&…...
C# 开发规范
控件命名规则 控件名简写 控件名简写LabellblTextBoxtxtButtonbtnLinkButtonlnkbtnImageButtonimgbtnDropDownListddlListBoxlstDataGriddgDataListdlCheckBoxchkCheckBoxListchklsRadioButtonrdoRadioButtonListrdoltImageimgPanelpnlCalendecldAdRotatorarTabletblRequiredF…...
【uniapp 样式】使用setStorageSync存储历史搜索记录
<template><view><view class"zhuangbox u-flex"><u--inputplaceholder"请输入关键字搜索"border"surround"shapecircleprefixIcon"search"prefixIconStyle"font-size: 22px;color: #909399"v-model&q…...
git remote add origin详解
git remote add origin详解_笔记大全_设计学院 一、git remote add origin的基础 使用“git remote add origin”指令,可以轻松地将本地项目连接到远程Git仓库 二、git remote add origin的用法 “git remote add origin”指令可以使用以下语法: git…...
Zustand 状态管理库:极简而强大的解决方案
Zustand 是一个轻量级、快速和可扩展的状态管理库,特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...
Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)
概述 在 Swift 开发语言中,各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过,在涉及到多个子类派生于基类进行多态模拟的场景下,…...
【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)
🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...
(转)什么是DockerCompose?它有什么作用?
一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用,而无需手动一个个创建和运行容器。 Compose文件是一个文本文件,通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...
Kafka主题运维全指南:从基础配置到故障处理
#作者:张桐瑞 文章目录 主题日常管理1. 修改主题分区。2. 修改主题级别参数。3. 变更副本数。4. 修改主题限速。5.主题分区迁移。6. 常见主题错误处理常见错误1:主题删除失败。常见错误2:__consumer_offsets占用太多的磁盘。 主题日常管理 …...
React从基础入门到高级实战:React 实战项目 - 项目五:微前端与模块化架构
React 实战项目:微前端与模块化架构 欢迎来到 React 开发教程专栏 的第 30 篇!在前 29 篇文章中,我们从 React 的基础概念逐步深入到高级技巧,涵盖了组件设计、状态管理、路由配置、性能优化和企业级应用等核心内容。这一次&…...
2025-06-01-Hive 技术及应用介绍
Hive 技术及应用介绍 参考资料 Hive 技术原理Hive 架构及应用介绍Hive - 小海哥哥 de - 博客园https://cwiki.apache.org/confluence/display/Hive/Home(官方文档) Apache Hive 是基于 Hadoop 构建的数据仓库工具,它为海量结构化数据提供类 SQL 的查询能力…...
Linux 中替换文件中的某个字符串
如果你想在 Linux 中替换文件中的某个字符串,可以使用以下命令: 1. 基本替换(sed 命令) sed -i s/原字符串/新字符串/g 文件名示例:将 file.txt 中所有的 old_text 替换成 new_text sed -i s/old_text/new_text/g fi…...
云原生技术驱动 IT 架构现代化转型:企业实践与落地策略全解
📝个人主页🌹:慌ZHANG-CSDN博客 🌹🌹期待您的关注 🌹🌹 一、背景:IT 架构演进的战略拐点 过去十年,企业 IT 架构经历了从传统集中式架构到分布式架构的转型。进入云计算…...
成工fpga(知识星球号)——精品来袭
(如需要相关的工程文件请关注知识星球:成工fpga,https://t.zsxq.com/DMeqH,关注即送200GB学习资料,链接已置顶!) 《孩子都能学会的FPGA》系列是成工完成的第一个系列,也有一年多的时…...
