C++---最长上升子序列模型---友好城市(每日一道算法2023.3.2)
注意事项:
本题为"线性dp—最长上升子序列的长度"的扩展题,所以dp思路这里就不再赘述。
题目:
Palmia国有一条横贯东西的大河,河有笔直的南北两岸,岸上各有位置各不相同的N个城市。
北岸的每个城市有且仅有一个友好城市在南岸,而且不同城市的友好城市不相同。
每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市,但是由于河上雾太大,政府决定避免任意两条航道交叉,以避免事故。
编程帮助政府做出一些批准和拒绝申请的决定,使得在保证任意两条航线不相交的情况下,被批准的申请尽量多。
输入格式
第1行,一个整数N,表示城市数。
第2行到第n+1行,每行两个整数,中间用1个空格隔开,分别表示南岸和北岸的一对友好城市的坐标。
输出格式
仅一行,输出一个整数,表示政府所能批准的最多申请数。
数据范围
1≤N≤5000,
0≤xi≤10000
输入:
7
22 4
2 6
10 3
15 12
9 8
17 17
4 2
输出:
4
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;const int N = 5010;
pair<int, int> w[N];
int f[N];
int n;//最长上升子序列模板,返回长度
int lis() {int res = 0;for (int i = 1; i<=n; i++) {f[i] = 1;for (int j = 1; j<i; j++) {if (w[j].second < w[i].second) f[i] = max(f[i], f[j] + 1);}res = max(res, f[i]);}return res;
}int main()
{//读入cin >> n;for (int i = 1; i<=n; i++) cin >> w[i].first >> w[i].second;//pair的排序默认就是按照第一个元素的大小由小到大,我这里写出来是复习一下, 大家直接sort(w+1, w+n+1)即可sort(w+1, w+n+1, [](auto a, auto b){return a.first < b.first;});cout << lis();return 0;
}
思路:
这道题的代码很简单,难点在于对于题目思路的转换
首先分析重点:
1.每个城市只能建一座桥
2.桥与桥不能相交
目标:问最多能建多少座桥
可以画出这样一个图:

图中的圆圈就是城市,每个城市在对岸都有其对应的友好城市,以绿线连接。
到这里就能看出一个重要性质了,将某一侧的城市位置进行排序后
在对岸的友好城市位置的最长上升子序列的长度 即为 桥最多能建立的数量。
这个性质是需要一些纯经验或者看脑袋的开窍程度才能在一定时间内想明白的,莫办法,多练吧呜呜呜
声明:
算法思路来源为y总,详细请见https://www.acwing.com/
本文仅用作学习记录和交流
相关文章:
C++---最长上升子序列模型---友好城市(每日一道算法2023.3.2)
注意事项: 本题为"线性dp—最长上升子序列的长度"的扩展题,所以dp思路这里就不再赘述。 题目: Palmia国有一条横贯东西的大河,河有笔直的南北两岸,岸上各有位置各不相同的N个城市。 北岸的每个城市有且仅有…...
maven高级知识。
目录 一、分模块开发 1、分模块开发设计 2、依赖管理 二、继承和聚合 1、聚合 2、继承 三、属性 1、基本介绍 2、版本管理 四、多环境配置与应用 1、多环境开发 2、跳过测试 五、私服 1、私服安装 2、私服仓库分类 一、分模块开发 1、分模块开发设计 ▶ 示意图 …...
Python 之 Pandas 处理字符串和apply() 函数、applymap() 函数、map() 函数详解
文章目录一、处理字符串1. 向量化字符串操作简介2. str 方法的简介二、apply() 函数详解三、applymap() 函数详解四、map() 函数详解一、处理字符串 当我们遇到一个超级大的 DataFrame,里面有一列类型为字符串,要将每一行的字符串都用同一方式进行处理&…...
汇川AM402和上位机C#ModebusTcp通讯
目录 一、测试任务 二、测试环境 三、PLC工程 1、组态配置 2、ip地址、端口号 3、全局变量定义 四、C#端Winform程序创建 1创建主界面 2、创建子窗口 3、运行生成,界面效果 4、Modebus协议说明 5、Modebus操作说明 六、测试 1、寄存器读测试 2、MW1300寄…...
给你一个电商网站,你如何测试?功能测试及接口测试思路是什么?
功能测试思路 1、注册测试: 测试注册表单是否可以正确提交用户信息; 测试注册表单是否有输入限制,例如密码长度、邮箱格式等; 测试注册后是否可以正常登录。 2、登录测试: 测试登录表单是否可以正确提交用户信息&…...
Spring Boot 3.0系列【5】基础篇之应用配置文件
有道无术,术尚可求,有术无道,止于术。 本系列Spring Boot版本3.0.3 源码地址:https://gitee.com/pearl-organization/study-spring-boot3 文章目录 前言应用配置文件文件格式YAML获取配置属性方式1:@Value方式2: @ConfigurationProperties方式3: @PropertySource方式4…...
SQLyog图形化界面工具【超详细讲解】
目录 一、SQLyog 介绍 二、SQLyog 社区版下载 三、SQLyog 安装 1、选择Chinese后点击OK 2、点击“下一步” 3、选择“我接受”后点击“下一步” 4、点击“下一步” 5、修改安装位置(尽量不要安装在C盘),点击“安装” 6、安装后点击“…...
Linux: 中断只被GIC转发到CPU0问题分析
文章目录1. 前言2. 分析背景3. 问题4. 分析4.1 ARM GIC 中断芯片简介4.1.1 中断类型和分布4.1.2 拓扑结构4.2 问题根因4.2.1 设置GIC SPI 中断CPU亲和性4.2.2 GIC初始化:缺省的CPU亲和性4.2.2.1 boot CPU亲和性初始化流程4.2.2.1 其它非 boot CPU亲和性初始化流程5.…...
模电学习10. MOS管简单应用电路
模电学习10. MOS管简单使应用电路一、开关和放大器1. 开关电路2. 放大电路二、时序电路中作为反相器使用三、双向电平转换电路1. 原理图2. 工作状态分析(1)分析SDA,信号从左向右(2)分析SDA,信号从右向左四、…...
轻松搞懂Linux中的用户管理
文章目录概念用户账户用户组用户权限用户管理工具概念 用户管理是Linux系统管理员必须掌握的重要技能之一。Linux系统是一个多用户操作系统,可以支持多个用户同时使用,每个用户拥有自己的账户和权限,因此管理员需要了解如何创建、管理和删除…...
力扣-丢失信息的雇员
大家好,我是空空star,本篇带大家了解一道简单的力扣sql练习题。 文章目录前言一、题目:1965. 丢失信息的雇员二、解题1.正确示范①提交SQL运行结果2.正确示范②提交SQL运行结果3.正确示范③提交SQL运行结果4.正确示范④提交SQL运行结果5.其他…...
FPGA采集AD7606全网最细讲解 提供串行和并行2套工程源码和技术支持
目录1、前言2、AD7606数据手册解读输入信号采集范围输出模式选择过采样率设置3、AD7606串行输出采集4、AD7606并行输出采集5、vivado仿真6、上板调试验证7、福利:工程代码的获取1、前言 AD7606是一款非常受欢迎的AD芯片,因为他支持8通道同时采集数据&am…...
CSS介绍
文章目录一. CSS介绍二. CSS的引入方式三. CSS选择器一. CSS介绍 定义: 层叠样式表作用: 美化界面: 设置标签文字大小,颜色,字体加粗等样式控制页面布局: 设置浮动,定位等样式 基本语法: 选择器{样式规则 } 样式规则: 属性名1: 属性值1 属性名2: 属性值2 属性名3: 属性值3 ..…...
Auto-encoder 系列
Auto-Encoder (AE)Auto-encoder概念自编码器要做的事:将高维的信息通过encoder压缩到一个低维的code内,然后再使用decoder对其进行重建。“自”不是自动,而是自己训练[1]。PCA要做的事其实与AE一样,只是没有神经网络。对于一个输入…...
【蓝桥杯入门不入土】变幻莫测的链表
文章目录一:链表的类型单链表双链表循环链表二:链表的存储方式三:链表的定义删除节点添加节点四:实战练习1.设计链表2. 移除链表元素最后说一句一:链表的类型 单链表 什么是链表,链表是一种通过指针串联在…...
axios的二次封装
方式一:将axios单独分装到某个配置文件中import axios from axios; const axiosApi axios.create({baseURL:http://127.0.0.1:3000,timeout:3000 }) export default axiosApi在组件中使用:import $http from axios配置文件的地址 $http.get(/student/test).then(re…...
GET与POST区别(最详细)
相同点:本质上都是TCP连接。 不同点:由于HTTP规定和服务器/浏览器限制,在应用过程中区别如下: 1.get产生一个TCP数据包,post 产生两个TCP数据包 get请求,浏览器会把http header和data一起发送,…...
精选博客系列|将基于决策树的Ensemble方法用于边缘计算
在即将到来的边缘计算时代,越来越需要边缘设备执行本地快速训练和分类的能力。事实上,无论是手机上的健康应用程序、冰箱上的传感器还是扫地机器人上的摄像头,由于许多原因,例如需要快速响应时间、增强安全性、数据隐私࿰…...
JS混淆加密:Eval的未公开用法
JavaScript奇技淫巧:Eval的未公开用法 作者:http://JShaman.com w2sft,转载请保留此信息很多人都知道,Eval是用来执行JS代码的,可以执行运算、可以输出结果。 但它还有一种未公开的用途,想必很少有人用过。…...
π型滤波器 计算_π型滤波电路
滤波器在功率和音频电子中常用于滤除不必要的频率。而电路设计中,基于不同应用有着许多不同种类的滤波器,但它们的基本理念都是一致的,那就是移除不必要的信号。所有滤波器都可以被分为两类,有源滤波器和无源滤波器。有源滤波器用…...
手游刚开服就被攻击怎么办?如何防御DDoS?
开服初期是手游最脆弱的阶段,极易成为DDoS攻击的目标。一旦遭遇攻击,可能导致服务器瘫痪、玩家流失,甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案,帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...
Linux简单的操作
ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...
Nuxt.js 中的路由配置详解
Nuxt.js 通过其内置的路由系统简化了应用的路由配置,使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...
06 Deep learning神经网络编程基础 激活函数 --吴恩达
深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...
系统掌握PyTorch:图解张量、Autograd、DataLoader、nn.Module与实战模型
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文通过代码驱动的方式,系统讲解PyTorch核心概念和实战技巧,涵盖张量操作、自动微分、数据加载、模型构建和训练全流程&#…...
医疗AI模型可解释性编程研究:基于SHAP、LIME与Anchor
1 医疗树模型与可解释人工智能基础 医疗领域的人工智能应用正迅速从理论研究转向临床实践,在这一过程中,模型可解释性已成为确保AI系统被医疗专业人员接受和信任的关键因素。基于树模型的集成算法(如RandomForest、XGBoost、LightGBM)因其卓越的预测性能和相对良好的解释性…...
32位寻址与64位寻址
32位寻址与64位寻址 32位寻址是什么? 32位寻址是指计算机的CPU、内存或总线系统使用32位二进制数来标识和访问内存中的存储单元(地址),其核心含义与能力如下: 1. 核心定义 地址位宽:CPU或内存控制器用32位…...
比特币:固若金汤的数字堡垒与它的四道防线
第一道防线:机密信函——无法破解的哈希加密 将每一笔比特币交易比作一封在堡垒内部传递的机密信函。 解释“哈希”(Hashing)就是一种军事级的加密术(SHA-256),能将信函内容(交易细节…...
华为OD机考- 简单的自动曝光/平均像素
import java.util.Arrays; import java.util.Scanner;public class DemoTest4 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint[] arr Array…...
