网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
木棍
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | wooden.in | 输出文件 | wooden.out |
【题目描述】
有n根木棍,每根的长度l和重量w已知。这些木棍将被一台机器一根一根的加工。机器需要一些启动时间来做准备工作,启动时间与木棍被加工的具体情况有关。启动时间遵循以下规则:
1加工第一根木棍的启动时间为1分钟。
2加工完长度为li,重量为wi的木棍后,紧跟着加工长度li+1,重量为wi+1的木棍时,若li≤li+1且wi≤wi+1,则加工木棍i+1时,不需要启动时间。例如:有5根木棍,它们的长度和重量对为(9,4),(2,5),(1,2),(5,3),(4,1),则最小总启动时间为 2分钟(加工序列为(4,1),(5,3),(9,4),(1,2),(2,5))。
【输入格式】
输入文件wooden.in
第一行一个整数n(1≤n≤5000),表示木棍的数量。
第二行2 * n个整数,l1,w1,l2,w2,.......,ln,wn(1≤li,wi≤10000),为各根木棍的长度和重量,这2 * n个整数以若干个空格分隔。
【输出格式】
输出文件wooden.out仅一行,一个整数,即最小总启动时间。
【样例输入1】
5
4 9 5 2 2 1 3 5 1 4
【样例输出1】
2【样例输入2】
3
2 2 1 1 2 2
【样例输出2】
1
【来源】
冲刺NOIP2010模拟试题与解析(七)(提高组复赛)