当前位置: 首页 > news >正文

上升点列

题目描述

在一个二维平面内,给定 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∼210010
3∼410100100
5∼75000100
8∼10500010^9
11∼15500100100
16∼2050010010^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小者小。

相关文章:

上升点列

题目描述 在一个二维平面内&#xff0c;给定 n 个整数点 (xi​,yi​)&#xff0c;此外你还可以自由添加 k 个整数点。 你在自由添加 k 个点后&#xff0c;还需要从 nk 个点中选出若干个整数点并组成一个序列&#xff0c;使得序列中任意相邻两点间的欧几里得距离恰好为 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商城首页小程序-代码生成器

在设计一个小程序的首页时&#xff0c;包含轮播图、通知栏和商品列表这三个元素是非常常见且有效的布局方式。这样的设计既能够吸引用户的注意力&#xff0c;又能够高效地展示信息和商品。 轮播组件 小程序首页幻灯片通常位于小程序的顶部或显著位置&#xff0c;通过滑动屏幕可…...

Vue3 富文本:WangEditor

wangEditor 开源 Web 富文本编辑器&#xff0c;开箱即用&#xff0c;配置简单 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&#xff08;k8s&#xff09;中最小的资源管理组件&#xff0c;也是最小化运行容器化应用的资源对象。以下是对Pod的详细介绍&#xff1a; 一、Pod的基本概念 定义&#xff1a;Pod是Kubernetes中可以创建和管理的最小单元&#xff0c;是资源对象模型中由用户创…...

软件测试面试题大全

什么是软件测试&#xff1f; 答案&#xff1a;软件测试是一系列活动&#xff0c;旨在评估软件产品的质量&#xff0c;并验证它是否满足规定的需求。它包括执行程序或系统以识别任何缺陷、问题或错误&#xff0c;并确保软件产品符合用户期望。 软件测试的目的是什么&#xff1f…...

SQL第16课挑战题

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

Python3 爬虫 中间人爬虫

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

Leetcode 50. Pow ( x , n ) 快速幂、取模 C++实现

问题&#xff1a;Leetcode 50. Pow ( x , n ) 实现 pow(x, n) &#xff0c;即计算 x 的整数 n 次幂函数。 算法&#xff1a; 具体实现流程如下&#xff1a; 代码&#xff1a; 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&#xff08;Java Platform&#xff0c;Standard Edition&#xff09;: Java 平台标准版&#xff0c;Java 编程语言的基础&#xff0c;它包含了支持 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 注释&#xff1a; priority1 #数字越小代表优先级越高&#xff…...

做一个不断更新的链接库

做一个不断更新的链接库 anaconda anaconda官方镜像源 anaconda清华镜像源 社区 CSDN CSDN-华为开发者空间 python开发库 股票爬虫 - akshare...

Ping32企业加密软件:保护数据安全

在数字化时代&#xff0c;数据安全已成为每个企业不可忽视的重要课题。无论是客户信息、财务报表&#xff0c;还是商业机密&#xff0c;数据的安全性直接关系到企业的声誉与运营。为了应对不断变化的安全威胁&#xff0c;选择一款可靠的企业加密软件尤为重要。在这里&#xff0…...

【Java】异常的处理-方式【主线学习笔记】

文章目录 前言1、处理概述2、Java异常处理机制&#xff08;方式&#xff09;方式一&#xff08;抓抛模型&#xff09;&#xff1a;try-catch-finally方式二&#xff1a;throws 异常类型总结 前言 Java是一门功能强大且广泛应用的编程语言&#xff0c;具有跨平台性和高效的执行…...

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+花生壳实现远程访问

有远程办公的需求&#xff0c;以及一些其他东西。 为什么写&#xff1f; 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 实现分布式锁:原理、实现与优化

在分布式系统中&#xff0c;分布式锁是确保多个进程或线程在同一时间内对共享资源进行互斥访问的重要机制。Redis 作为一个高性能的内存数据库&#xff0c;提供了多种实现分布式锁的方式。本文将详细介绍如何使用 Redis 实现分布式锁&#xff0c;包括基本原理、实现方法、示例代…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建

华为云FlexusDeepSeek征文&#xff5c;DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色&#xff0c;华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型&#xff0c;能助力我们轻松驾驭 DeepSeek-V3/R1&#xff0c;本文中将分享如何…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

HDFS分布式存储 zookeeper

hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架&#xff0c;允许使用简单的变成模型跨计算机对大型集群进行分布式处理&#xff08;1.海量的数据存储 2.海量数据的计算&#xff09;Hadoop核心组件 hdfs&#xff08;分布式文件存储系统&#xff09;&a…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...

现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?

现有的 Redis 分布式锁库&#xff08;如 Redisson&#xff09;相比于开发者自己基于 Redis 命令&#xff08;如 SETNX, EXPIRE, DEL&#xff09;手动实现分布式锁&#xff0c;提供了巨大的便利性和健壮性。主要体现在以下几个方面&#xff1a; 原子性保证 (Atomicity)&#xff…...

深度学习之模型压缩三驾马车:模型剪枝、模型量化、知识蒸馏

一、引言 在深度学习中&#xff0c;我们训练出的神经网络往往非常庞大&#xff08;比如像 ResNet、YOLOv8、Vision Transformer&#xff09;&#xff0c;虽然精度很高&#xff0c;但“太重”了&#xff0c;运行起来很慢&#xff0c;占用内存大&#xff0c;不适合部署到手机、摄…...