【2022CSPJ普及组】 T4.上升点列（point）

9月前作者：宏阳李老师分类：Toy博客阅读(38) 违法举报

这篇具有很好参考价值的文章主要介绍了【2022CSPJ普及组】 T4.上升点列（point）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

【2022CSPJ普及组】 T4.上升点列（point）
【题目描述】
在一个二维平面内，给定 n 个整数点 (xi, yi)，此外你还可以自由添加 k 个整数点。
你在自由添加 k 个点后，还需要从 n + k 个点中选出若干个整数点并组成一个序列，使得序列中任意相邻两点间的欧几里得距离恰好为 1 而且横坐标、纵坐标值均单调不减，即 x(i+1) − xi = 1, y(i+1) = yi 或 y(i+1) − yi = 1, x(i+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，且保证所有给定的点互不重合。对于自由添加的整点，其横纵坐标不受限制。

题目解析：文章来源地址https://www.toymoban.com/news/detail-605898.html

到了这里，关于【2022CSPJ普及组】 T4.上升点列（point）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：

领支付宝红包赞助服务器费用

历年CSP-J（NOIP普及组）考点分析与分类汇总

持续更新中.... CSP-J (NOIP 普及组 ) 历年复赛真题考察内容 (1998 ～ 2023) 考点分析： CSP-J (NOIP 普及组 ) -T1知识点统计年份题目名考点 2010 数字统计整数拆分，数位分离 2011 数字反转整数拆分，数位分离 2012 质因数分解质因数分解 2013 计数问题整数拆分，数位分离 2014 珠心算

2024年02月20日
浏览(43)
[NOIP2002 普及组] 选数#洛谷

已知 n n n 个整数 x 1 , x 2 , ⋯ , x n x_1,x_2,cdots,x_n x 1 , x 2 , ⋯ , x n ，以及 1 1 1 个整数 k k k （ k n kn k n ）。从 n n n 个整数中任选 k k k 个整数相加，可分别得到一系列的和。例如当 n = 4 n=4 n = 4 ， k = 3 k=3 k = 3 ， 4 4 4 个整数分别为 3 , 7 , 12 , 19 3,7,12,19 3 , 7 , 12 , 19 时，

2024年01月20日
浏览(46)
一本通1919：【02NOIP普及组】选数

这道题感觉很好玩。先放题目：信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn) http://ybt.ssoier.cn:8088/problem_show.php?pid=1919 已知 n 个整数 x1,x2,…,xn，以及一个整数 k（k＜n）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n=4，k＝3，4 个整数分别为 3，7，

2024年02月16日
浏览(34)
[NOIP2007 普及组] 纪念品分组

元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间

2024年02月14日
浏览(44)
[NOIP2004 普及组] FBI 树队列解法

我们可以把由 0 和 1 组成的字符串分为三类：全 0 串称为 B 串，全 1 串称为 I 串，既含 0 又含 1 的串则称为 F 串。 FBI 树是一种二叉树，它的结点类型也包括 F 结点，B 结点和 I 结点三种。由一个长度为 $2^N$ 的 01 串 S 可以构造出一棵 FBI 树 T，递归的构造方法如下： 1. T 的根

2024年02月07日
浏览(91)
#P0999. [NOIP2008普及组] 排座椅

上课的时候总会有一些同学和前后左右的人交头接耳，这是令小学班主任十分头疼的一件事情。不过，班主任小雪发现了一些有趣的现象，当同学们的座次确定下来之后，只有有限的 DD 对同学上课时会交头接耳。同学们在教室中坐成了 MM 行 NN 列，坐在第 ii 行第 jj 列

2024年02月15日
浏览(45)
NOIP2003普及组复赛T2：数字游戏

题目链接：NOIP2003普及组复赛T2 - 数字游戏丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单，但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的，在你面前有一圈整数（一共 n n n 个），你要按顺序将其分为 m m m 个部分

2024年02月09日
浏览(40)
P1077 [NOIP2012 普及组] 摆花题解

小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共 m m m 盆。通过调查顾客的喜好，小明列出了顾客最喜欢的 n n n 种花，从 1 1 1 到 n n n 标号。为了在门口展出更多种花，规定第 i i i 种花不能超过 a i a_i a i 盆，摆花时同一种花放在一起，且不同种类的花

2024年02月08日
浏览(45)
搜索？——P3956 [NOIP2017 普及组] 棋盘

传送门: [NOIP2017 普及组] 棋盘 - 洛谷思路: 将棋盘的每一个格子看做一个点，建一个无向图用来跑最短路. 这道题本应用搜索来做，但是转换成最短路好像简单点建图: 1.对于已经有颜色的格子，在扫描四个方向的格子对相同颜色的建条长度为0的边，不同颜色的建条长度为1的

2024年02月01日
浏览(35)
[NOIP2009 普及组] 分数线划定#洛谷

世博会志愿者的选拔工作正在 A 市如火如荼的进行。为了选拔最合适的人才，A 市对所有报名的选手进行了笔试，笔试分数达到面试分数线的选手方可进入面试。面试分数线根据计划录取人数的 150 % 150% 150% 划定，即如果计划录取 m m m 名志愿者，则面试分数线为排名第 m ×

2024年01月17日
浏览(38)