J4 习题-4 木棍加工

题目描述

一堆木头棍子共 $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$。