/ Vijos / 题库 /

排队

排队

时间限制:1秒  内存限制:256M


【问题描述】

  你需要从 \(n\) 名学生中选出尽可能多的人排成一队,要求排成的队伍身高和体重 不上升。请你编程计算最多能选出多少人?
  注意:对挑出的学生,可以按你的需要重新给他们排队!

【输入格式】

  第一行一个正整数 \(n\) ,表示学生数目。
  接下来的 \(n\) 行,每行有两个整数,第 \(i+1\) 行的第一个整数表示第 \(i\) 名学生的身高 \(h_i\),第二个整数表示学生 \(i\) 的体重 \(w_i\)。

【输出格式】

  只有一行,为队列中最多的学生数量。

【输入输出样例】

 Input

5 
5 3
7 6
3 7
6 3
8 2

 Output

3

【输入输出样例解释】

  选择(5,3)、(7,6)、(6,3)这3位学生,排成(7,6)、(6,3)、(5,3),这样保证了身高和体重均是不上升的。

【数据说明】

  对于 \(100\%\) 的数据 \(1≤n≤100000\),\(1≤h_i,w_i≤2147483647\)。

【来源】

  Mr.he

信息

ID
1647
难度
9
分类
动态规划 | LIS 点击显示
标签
(无)
递交数
2
已通过
1
通过率
50%
被复制
6
上传者