P1177 - [CSP-J 2022] 上升点列

文件提交：无需freopen 内存限制：512 MB 时间限制：1.000 S

评测方式：普通裁判命题人：

提交：1 解决：1

在一个二维平面内，给定 $lns="http://www.w3.org/1998/Math/MathML"> �$ 个整数点 $lns="http://www.w3.org/1998/Math/MathML"> (�_{�}, �_{�})$ ，此外你还可以自由添加 $lns="http://www.w3.org/1998/Math/MathML"> �$ 个整数点。

你在自由添加 $lns="http://www.w3.org/1998/Math/MathML"> �$ 个点后，还需要从 $lns="http://www.w3.org/1998/Math/MathML"> � + �$ 个点中选出若干个整数点并组成一个序列，使得序列中任意相邻两点间的欧几里得距离恰好为 $lns="http://www.w3.org/1998/Math/MathML"> 1$ 而且横坐标、纵坐标值均单调不减，即 $lns="http://www.w3.org/1998/Math/MathML"> �_{� + 1} - �_{�} = 1, �_{� + 1} = �_{�}$ 或 $lns="http://www.w3.org/1998/Math/MathML"> �_{� + 1} - �_{�} = 1, �_{� + 1} = �_{�}$ 。请给出满足条件的序列的最大长度。

第一行两个正整数 $lns="http://www.w3.org/1998/Math/MathML"> �, �$ 分别表示给定的整点个数、可自由添加的整点个数。

接下来 $lns="http://www.w3.org/1998/Math/MathML"> �$ 行，第 $lns="http://www.w3.org/1998/Math/MathML"> �$ 行两个正整数 $lns="http://www.w3.org/1998/Math/MathML"> �_{�}, �_{�}$ 表示给定的第 $lns="http://www.w3.org/1998/Math/MathML"> �$ 个点的横纵坐标。

输出一个整数表示满足要求的序列的最大长度。

保证对于所有数据满足： $lns="http://www.w3.org/1998/Math/MathML"> 1 \leq � \leq 500$ ， $lns="http://www.w3.org/1998/Math/MathML"> 0 \leq � \leq 100$ 。对于所有给定的整点，其横纵坐标 $lns="http://www.w3.org/1998/Math/MathML"> 1 \leq �_{�}, �_{�} \leq 10^{9}$ ，且保证所有给定的点互不重合。对于自由添加的整点，其横纵坐标不受限制。

测试点编号	$lns="http://www.w3.org/1998/Math/MathML"> � \leq$	$lns="http://www.w3.org/1998/Math/MathML"> � \leq$	$lns="http://www.w3.org/1998/Math/MathML"> �_{�}, �_{�} \leq$
$lns="http://www.w3.org/1998/Math/MathML"> 1 \sim 2$	$lns="http://www.w3.org/1998/Math/MathML"> 10$	$lns="http://www.w3.org/1998/Math/MathML"> 0$	$lns="http://www.w3.org/1998/Math/MathML"> 10$
$lns="http://www.w3.org/1998/Math/MathML"> 3 \sim 4$	$lns="http://www.w3.org/1998/Math/MathML"> 10$	$lns="http://www.w3.org/1998/Math/MathML"> 100$	$lns="http://www.w3.org/1998/Math/MathML"> 100$
$lns="http://www.w3.org/1998/Math/MathML"> 5 \sim 7$	$lns="http://www.w3.org/1998/Math/MathML"> 500$	$lns="http://www.w3.org/1998/Math/MathML"> 0$	$lns="http://www.w3.org/1998/Math/MathML"> 100$
$lns="http://www.w3.org/1998/Math/MathML"> 8 \sim 10$	$lns="http://www.w3.org/1998/Math/MathML"> 500$	$lns="http://www.w3.org/1998/Math/MathML"> 0$	$lns="http://www.w3.org/1998/Math/MathML"> 10^{9}$
$lns="http://www.w3.org/1998/Math/MathML"> 11 \sim 15$	$lns="http://www.w3.org/1998/Math/MathML"> 500$	$lns="http://www.w3.org/1998/Math/MathML"> 100$	$lns="http://www.w3.org/1998/Math/MathML"> 100$
$lns="http://www.w3.org/1998/Math/MathML"> 16 \sim 20$	$lns="http://www.w3.org/1998/Math/MathML"> 500$	$lns="http://www.w3.org/1998/Math/MathML"> 100$	$lns="http://www.w3.org/1998/Math/MathML"> 10^{9}$

模拟 CSP-J DP

提交提交记录统计露一手!

1177: [CSP-J 2022] 上升点列

题目描述

输入

输出

样例输入

样例输出

提示

来源/分类