上升点列
题目描述
在一个二维平面内,给定 n 个整数点 (xi,yi),此外你还可以自由添加 k 个整数点。
你在自由添加 k 个点后,还需要从 n+k 个点中选出若干个整数点并组成一个序列,使得序列中任意相邻两点间的欧几里得距离恰好为 1 而且横坐标、纵坐标值均单调不减,即 xi+1−xi=1,yi+1=yi 或 yi+1−yi=1,xi+1=xi。请给出满足条件的序列的最大长度。
输入格式
第一行两个正整数 n,k 分别表示给定的整点个数、可自由添加的整点个数。
接下来 n 行,第 i 行两个正整数 xi,yi 表示给定的第 i 个点的横纵坐标。
输出格式
输出一个整数表示满足要求的序列的最大长度。
输入输出样例
输入 #1
8 2 3 1 3 2 3 3 3 6 1 2 2 2 5 5 5 3
输出 #1
8
输入 #2
4 100 10 10 15 25 20 20 30 30
输出 #2
103
说明/提示
【数据范围】
保证对于所有数据满足:1≤n≤500,0≤k≤100。对于所有给定的整点,其横纵坐标 1≤xi,yi≤10^9,且保证所有给定的点互不重合。对于自由添加的整点,其横纵坐标不受限制。
测试点编号 | n≤ | k≤ | xi,yi≤ |
---|---|---|---|
1∼2 | 10 | 0 | 10 |
3∼4 | 10 | 100 | 100 |
5∼7 | 500 | 0 | 100 |
8∼10 | 500 | 0 | 10^9 |
11∼15 | 500 | 100 | 100 |
16∼20 | 500 | 100 | 10^9 |
#include <bits/stdc++.h>
using namespace std;struct node
{int x,y;//1e9 1e9
};
bool operator<(node n1,node n2)
{return n1.x<n2.x||(n1.x==n2.x&&n1.y<n2.y);
}
node p[510];//5e2
int dp[510][110];//5e2
int main()
{int n,k;//5e2 1e2cin>>n>>k;for(int i=1;i<=n;i++){int x,y;//1e9 1e9cin>>x>>y;p[i]={x,y};}sort(p+1,p+n+1);int maxn=0;//5e2for(int i=1;i<=n;i++){int x=p[i].x,y=p[i].y;for(int l=0;l<=k;l++){for(int j=1;j<i;j++){int dx=x-p[j].x,dy=y-p[j].y;if(dx>=0&&dy>=0&&dx+dy<=l+1)dp[i][l]=max(dp[i][l],dp[j][l-dx-dy+1]+dx+dy);}if(dp[i][l]==0)dp[i][l]=l+1;maxn=max(maxn,dp[i][l]);}}cout<<maxn;return 0;
}
---------------------------------------前方级别:洛谷黄题,2022CSP-J T3---------------------------------------
主体思想及算法:
DP中的LIS(最长上升子序列)变形。
LIS模板:
for(int i=1;i<=n;i++)
{dp[i]=1;for(int j=1;j<i;j++)if(a[i]>a[j])dp[i]=max(dp[i],dp[j]+1);maxn=max(maxn,dp[i]);
}
cout<<maxn;
变形后dp[i][j]代表第i个点加j个点的最大答案。
代码解读:
main():输入n、k、xi、yi。xi和yi记录在一个node(见node)类型的p数组里,p[i]代表编号为i的一组xy。但是由于下方某些原因,p数组不得使用原顺序,需要按排序(具体规则见operator<())后的顺序。排序后定义一个maxn,由于此题为LIS变形,这个maxn自然代表答案啦!不过初始置为k+1,因为但凡有一个点,他添加k个点也有k+1了。
第一层循环:首先不管加点的事儿,先定义xy分别为p[i]的xy,一会儿将多次使用。
第二层循环:请注意,这层循环的变量l代表可以加l个点,是从0到k!!!因为你可以选择独自优秀不须加点。
第三层循环:这个j也要注意,是到i-1,由于之前的排序,我们保证到i之后肯定都不行了,所以也都没用了。再设两个临时变量dx和dy,代表x-p[j].x和y-p[j].y(同样,一会儿将多次使用)。如果dx和dy均大于等于0,也就是说按照要求可以连线,且dx加dy小于等于l加1,这里注意加1,因为假设l是0,dx加dy就得是1。如果满足上句话这些条件,那么dp[i][j]就max=dp[j][l-dx-dy+1]+dx+dy。
回到第二层循环,因为每一个dp[i][l]都是独立的,所以maxn等要在此处单独结算。注意如果dp[i][l]是0,要给他设为l+1,毕竟添加l个点就有l+1了。最后maxn max=dp[i][l]。
回到主函数,输出maxn。
node:一个x一个y。
operator<():重载小于运算符,如果x不同x小者小;否则y小者小。
相关文章:
上升点列
题目描述 在一个二维平面内,给定 n 个整数点 (xi,yi),此外你还可以自由添加 k 个整数点。 你在自由添加 k 个点后,还需要从 nk 个点中选出若干个整数点并组成一个序列,使得序列中任意相邻两点间的欧几里得距离恰好为 1 而且…...

刷题 链表
面试经典150题 - 链表 141. 环形链表 class Solution { public:bool hasCycle(ListNode *head) {ListNode* slow head, *fast head;while (fast ! nullptr && fast->next ! nullptr) {slow slow->next;fast fast->next->next;if (slow fast) {return…...
SQL 语法学习指南
目录 前言1. SQL 的基本概念1.1 SQL 的作用1.2 SQL 的特点 2. SQL 的基础语法2.1 数据查询 - SELECT 语句2.2 数据插入 - INSERT 语句2.3 数据更新 - UPDATE 语句2.4 数据删除 - DELETE 语句 3. SQL 的进阶语法3.1 聚合函数3.2 表连接 - JOIN3.3 子查询 4. SQL 学习建议4.1 多实…...

低代码可视化-uniapp商城首页小程序-代码生成器
在设计一个小程序的首页时,包含轮播图、通知栏和商品列表这三个元素是非常常见且有效的布局方式。这样的设计既能够吸引用户的注意力,又能够高效地展示信息和商品。 轮播组件 小程序首页幻灯片通常位于小程序的顶部或显著位置,通过滑动屏幕可…...
Vue3 富文本:WangEditor
wangEditor 开源 Web 富文本编辑器,开箱即用,配置简单 wangEditor 1. 安装依赖包 npm install wangeditor/editor-for-vuenext --save 2. 在引用页面加入如下代码 <template><div style"border: 1px solid #ccc"><Toolbar …...

Unity实现自定义图集(四)
以下内容是根据Unity 2020.1.0f1版本进行编写的 在之前的篇章中已经把自定义图集在编辑器上的使用,以及运行时所需的信息都准备好了,接下来就是魔改UGUI的Image组件,使其能够像Image那样运行时如果引用的资源有打自定义图集,则加载对应自定义图集的Texture。 1、思路 …...

k8s-pod的管理及优化设置
Pod是Kubernetes(k8s)中最小的资源管理组件,也是最小化运行容器化应用的资源对象。以下是对Pod的详细介绍: 一、Pod的基本概念 定义:Pod是Kubernetes中可以创建和管理的最小单元,是资源对象模型中由用户创…...
软件测试面试题大全
什么是软件测试? 答案:软件测试是一系列活动,旨在评估软件产品的质量,并验证它是否满足规定的需求。它包括执行程序或系统以识别任何缺陷、问题或错误,并确保软件产品符合用户期望。 软件测试的目的是什么?…...

SQL第16课挑战题
1. 美国各州的缩写应始终用大写。更新所有美国地址,包括供应商状态(Vendors表中的vend_state)和顾客状态(customers表中的cust_state),使它们均为大写。 2. 第15课挑战题1要求将自己添加到customers表中,现在删除自己,…...

Python3 爬虫 中间人爬虫
中间人(Man-in-the-Middle,MITM)攻击是指攻击者与通信的两端分别创建独立的联系,并交换其所收到的数据,使通信的两端认为其正在通过一个私密的连接与对方直接对话,但事实上整个会话都被攻击者完全控制。在中…...

Leetcode 50. Pow ( x , n ) 快速幂、取模 C++实现
问题:Leetcode 50. Pow ( x , n ) 实现 pow(x, n) ,即计算 x 的整数 n 次幂函数。 算法: 具体实现流程如下: 代码: class Solution { public:double myPow(double x, int N) {double ans 1;long long n N;if (n <…...

Java SE vs Java EE 与 JVM vs JDK vs JRE
Java SE(Java Platform,Standard Edition): Java 平台标准版,Java 编程语言的基础,它包含了支持 Java 应用程序开发和运行的核心类库以及虚拟机等核心组件。Java SE 可以用于构建桌面应用程序或简单的服务器应用程序。…...

Linux YUM设置仓库优先级
1.安装yum-plugin-priorities优先级插件 yum install yum-plugin-priorities -y 2.设置仓库优先级 vim /etc/yum.repos.d/local.repo [local] namecentos7.5 baseurlfile:///mnt enable1 gpgcheck0 priority1 注释: priority1 #数字越小代表优先级越高ÿ…...
做一个不断更新的链接库
做一个不断更新的链接库 anaconda anaconda官方镜像源 anaconda清华镜像源 社区 CSDN CSDN-华为开发者空间 python开发库 股票爬虫 - akshare...

Ping32企业加密软件:保护数据安全
在数字化时代,数据安全已成为每个企业不可忽视的重要课题。无论是客户信息、财务报表,还是商业机密,数据的安全性直接关系到企业的声誉与运营。为了应对不断变化的安全威胁,选择一款可靠的企业加密软件尤为重要。在这里࿰…...
【Java】异常的处理-方式【主线学习笔记】
文章目录 前言1、处理概述2、Java异常处理机制(方式)方式一(抓抛模型):try-catch-finally方式二:throws 异常类型总结 前言 Java是一门功能强大且广泛应用的编程语言,具有跨平台性和高效的执行…...
React modal暴露ref简洁使用
父组件使用 import { useRef } from react import { FormModal } from ./modalconst IndexRoute () > {const formRef useRef<any>()const openModal (row?: any) > {const params {title: row?.id ? 【${row.name}】编辑 : 创建,isView: false,row,api: r…...

小米路由器ax1500+DDNS+公网IP+花生壳实现远程访问
有远程办公的需求,以及一些其他东西。 为什么写? ax1500路由器好像没搜到相关信息。以及其中有一点坑。 前置 公网ip Xiaomi路由器 AX1500 MiWiFi 稳定版 1.0.54 实现流程 花生壳申请壳域名https://console.hsk.oray.com/ 这里需要为域名实名认证 …...

毕设分享 大数据用户画像分析系统(源码分享)
文章目录 0 前言2 用户画像分析概述2.1 用户画像构建的相关技术2.2 标签体系2.3 标签优先级 3 实站 - 百货商场用户画像描述与价值分析3.1 数据格式3.2 数据预处理3.3 会员年龄构成3.4 订单占比 消费画像3.5 季度偏好画像3.6 会员用户画像与特征3.6.1 构建会员用户业务特征标签…...
使用 Redis 实现分布式锁:原理、实现与优化
在分布式系统中,分布式锁是确保多个进程或线程在同一时间内对共享资源进行互斥访问的重要机制。Redis 作为一个高性能的内存数据库,提供了多种实现分布式锁的方式。本文将详细介绍如何使用 Redis 实现分布式锁,包括基本原理、实现方法、示例代…...
【杂谈】-递归进化:人工智能的自我改进与监管挑战
递归进化:人工智能的自我改进与监管挑战 文章目录 递归进化:人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管?3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

大话软工笔记—需求分析概述
需求分析,就是要对需求调研收集到的资料信息逐个地进行拆分、研究,从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要,后续设计的依据主要来自于需求分析的成果,包括: 项目的目的…...
椭圆曲线密码学(ECC)
一、ECC算法概述 椭圆曲线密码学(Elliptic Curve Cryptography)是基于椭圆曲线数学理论的公钥密码系统,由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA,ECC在相同安全强度下密钥更短(256位ECC ≈ 3072位RSA…...

Appium+python自动化(十六)- ADB命令
简介 Android 调试桥(adb)是多种用途的工具,该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具,其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利,如安装和调试…...
PHP和Node.js哪个更爽?
先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢
随着互联网技术的飞速发展,消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁,不仅优化了客户体验,还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用,并…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业
6月9日,国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解,“超级…...

c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...