1375: 零件分组

内存限制:128 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:32 通过:18

题目描述

某工厂生产一批棍装零件,每个零件都有一定的长度(li)和重量(wi).现在为了加工需要,要将它们分成若干组,使每一组的零件都能排成一个长度和重量都不下降(若i<j,则li<=lj,wi<=wj)的序列。请问至少要分成几组。

输入格式

第一行为一个整数n(n<=1000),表示零件的个数。第二行有n对正整数,每对正整数表示这些零件的长度和重量,长度和重量均不超过10000.

输出格式

仅一行,即最少分成的组数。

输入样例 复制

5
8 4
3 8
2 3
9 7
3 5

输出样例 复制

2

数据范围与提示

二级排序

分类标签