#21579. J4 习题-7 木棍加工

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: xiongyingjie

题目描述

一堆木头棍子共 n 根,棍子的长度和宽度都是已知的。 棍子可以被一台机器一个接一个地加工。机器处理一根棍子之前需要准备时间。准备时间是这样定义的: 第一根棍子的准备时间为 1 分钟; 如果刚处理完长度为 L ,宽度为 W 的棍子,那么如果下一个棍子长度为 L_i ,宽度为 W_i ,并且满足 L_i \leq L W_i \leq W ,这个棍子就不需要准备时间,否则需要 1 分钟的准备时间; 请编程计算出,处理完 n 根棍子所需要的最短准备时间。 比如,有 5 根棍子,长度和宽度分别为 (4, 9),(5, 2),(2, 1),(3, 5),(1, 4) ,最短准备时间为 2 (按 (4, 9),(3, 5),(1, 4),(5, 2),(2, 1) 的次序进行加工)。

输入格式

第一行是一个整数 n , 第 2 行是 2n 个整数,分别是 L_1 , W_1 , L_2 , W_2 ,... ,L_n,W_n 。( L W 的值均不超过 10000 相邻两数之间用空格分开)。

输出格式

一个整数,表示所需要的最短准备时间。

样例

5
4 9 5 2 2 1 3 5 1 4

2

数据范围与提示

对于 100% 的数据: 1\leq n \leq 5000