木棍加工

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 sticks.in 输出文件 sticks.out

【问题描述】

一堆木头棍子共有n根,每根棍子的长度和宽度都是已知的。棍子可以被一台机器一个接一个地加工。机器处理一根棍子之前需要准备时间。准备时间是这样定义的:

第一根棍子的准备时间为1分钟;

如果刚处理完长度为L,宽度为W的棍子,那么如果下一个棍子长度为Li,宽度为Wi,并且满足L>LiW>Wi,这个棍子就不需要准备时间,否则需要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(n<5000),第2行是2n个整数,分别是L1W1L2w2,…,LnWnLW的值均不超过10000,相邻两数之间用空格分开。

【输出】

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

【样例】

stick.in

5

4 9 5 2 2 1 3 5 1 4

stick.out