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…...
实战应用:基于快马平台开发排序算法性能对比分析工具
今天想和大家分享一个特别实用的工具开发经历——用InsCode(快马)平台快速搭建了一个排序算法性能对比分析工具。这个项目不仅帮我巩固了算法知识,还意外发现了很多实际应用中的细节问题,特别适合用来理解不同排序算法的实战表现。 1. 为什么需要这个工…...
dockerc故障排除终极指南:10个常见错误和解决方案清单
dockerc故障排除终极指南:10个常见错误和解决方案清单 【免费下载链接】dockerc container image to single executable compiler 项目地址: https://gitcode.com/gh_mirrors/do/dockerc dockerc作为一款container image to single executable compiler工具&…...
[iPhone USB网络共享]完全指南:从驱动故障到高效连接
[iPhone USB网络共享]完全指南:从驱动故障到高效连接 【免费下载链接】Apple-Mobile-Drivers-Installer Powershell script to easily install Apple USB and Mobile Device Ethernet (USB Tethering) drivers on Windows! 项目地址: https://gitcode.com/gh_mirr…...
春招已经过半,这一波再不动手,基本就没位置了
关注 霍格沃兹测试学院公众号,回复「资料」,领取人工智能测试开发技术合集导读3月底这个时间点,如果你还在纠结“要不要投”,那基本已经慢半拍了。现在的真实情况是:大厂已经进入筛选面试并行阶段一部分公司已经开始发…...
从ATE到RPE:用evo全面解读你的SLAM算法在KITTI上的表现
从ATE到RPE:用evo全面解读你的SLAM算法在KITTI上的表现 在SLAM算法开发中,量化评估是验证算法性能的关键环节。KITTI数据集作为自动驾驶领域最具影响力的基准测试平台之一,为研究者提供了丰富的真实场景数据。但如何从海量轨迹数据中提取有价…...
5分钟搞懂线结构光三维重建:从激光平面到深度信息的完整流程
线结构光三维重建:从激光平面到深度信息的实战解析 当你第一次看到激光线扫过物体表面时,可能不会想到这条细细的光线背后隐藏着精确测量物体三维形状的能力。线结构光三维重建技术正悄然改变着工业检测、逆向工程和医疗影像等领域——它不需要接触物体…...
基于鲸鱼优化算法改进XGBoost在MATLAB中的时间序列预测性能(迭代次数、最大深度和学习...
基于鲸鱼优化算法优化XGBoost(WOA-XGBoost)的时间序列预测 WOA-XGBoost时间序列 采用交叉验证抑制过拟合问题 优化参数为迭代次数、最大深度和学习率 matlab代码,注:暂无Matlab版本要求 -- 推荐 2016B 版本及以上 注:采用 XGBoost 工具箱&…...
3分钟让Windows文件资源管理器焕然一新:ExplorerBlurMica毛玻璃效果完全指南
3分钟让Windows文件资源管理器焕然一新:ExplorerBlurMica毛玻璃效果完全指南 【免费下载链接】ExplorerBlurMica Add background Blur effect or Acrylic (Mica for win11) effect to explorer for win10 and win11 项目地址: https://gitcode.com/gh_mirrors/ex/…...
Linux 内核遍历宏介绍
Linux内核中的遍历宏全面详解 Linux内核中大量使用遍历宏(Iteration Macros)来简化数据结构的遍历操作。这些宏提供了类型安全、简洁且高效的遍历方式,是内核编程的核心范式之一。一、遍历宏的分类 1.1 按功能分类 Linux内核遍历宏 ├── 链…...
PyTorch 2.8镜像实际效果:torch.compile+FlashAttention-2双优化下的吞吐量提升对比
PyTorch 2.8镜像实际效果:torch.compileFlashAttention-2双优化下的吞吐量提升对比 1. 镜像环境与技术亮点 PyTorch 2.8深度学习镜像为开发者提供了一个开箱即用的高性能计算环境。基于RTX 4090D 24GB显卡和CUDA 12.4的深度优化组合,这个镜像特别适合需…...
