Algorithm 版 (精华区)

发信人: lizhenguo (夸父·追日), 信区: Algorithm
标  题: 韩国大田的题目
发信站: 哈工大紫丁香 (2001年12月04日18:45:57 星期二), 站内信件

这个题目很有意思，贴出来让大家讨论讨论
木头棍子
源程序名 　　　STICK.??? (pas,c,cpp)
可执行文件名  STICK.exe
输入文件名　　 STICK.in
输出文件名    STICK.out
一堆木头棍子共有n根，每根棍子的长度和重量都是已知的。棍子可以被一台机器一个接
一个地加工。机器处理一根棍子之前需要准备时间。准备时间是这样定义的：
(a) 第一根棍子的准备时间为1分钟；
(b) 如果刚处理完长度为L，重量为W的棍子，那么如果下一个棍子长Li，宽Wi，并且满足
L>=Li,W>=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个整数，分别是L1,W1,L2,W2,…,Ln,Wn。L和
W的值均不超过10000，相邻两数之间用空格分开。
输出
仅一行，一个整数，所需要的最短时间。
样例
STICK.IN
5
4 9 5 2 2 1 3 5 1 4
STICK.OUT
2
下面是英文原题
The 26 th Annual
ACM International Collegiate
Programming Contest
ASIA Regional - Taejon
Problem B
Wooden Sticks
Input: stick.in
There is a pile of n wooden sticks. The length and weight of each stick are kn
own in advance. The sticks are
to be processed by a woodworking machine in one by one fashion. It needs some
time, called setup time, for
the machine to prepare processing a stick. The setup times are associated with
cleaning operations and
changing tools and shapes in the machine. The setup times of the woodworking m
achine are given as follows:
(a) The setup time for the first wooden stick is 1 minute.
(b) Right after processing a stick of length l and weight w , the machine will
need no setup time for a stick
of length ' l and weight ' w if ' l l &pound; and ' w w &pound; . Otherwise, i
t will need 1 minute for setup.
You are to find the minimum setup time to process a given pile of n wooden sti
cks. For example, if you have
five sticks whose pairs of length and weight are ) 9 , 4 ( , ) 2 , 5 ( , ) 1 ,
2 ( , ) 5 , 3 ( , and ) 4 , 1 ( , then the minimum setup
time should be 2 minutes since there is a sequence of pairs ) 4 , 1 ( , ) 5 ,
3 ( , ) 9 , 4 ( , ) 1 , 2 ( , ) 2 , 5 ( .
Input
The input consists of T test cases. The number of test cases ) (T is given in
the first line of the input file. Each
test case consists of two lines: The first line has an integer n , 5000 1 &pou
nd; &pound; n , that represents the number of
wooden sticks in the test case, and the second line contains n 2 positive inte
 , n l , n w ,
each of magnitude at most 10000 , where i l and i w are the length and weight
of the i th wooden stick,
respectively. The n 2 integers are delimited by one or more spaces.
Output
The output should contain the minimum setup time in minutes, one per line.
Sample Input
(stick.in)
Output for the Sample Input
3
5
4 9 5 2 2 1 3 5 1 4
3
2 2 1 1 2 2
3
1 3 2 2 3 1
2
1
3
gers 1 l , 1 w , 2 l , 2 w , 
--
《列子·汤问》：“夸父不量力，欲追日影，逐之于隅谷之际。渴欲 得饮，赴饮河渭
。河渭不足，将走北饮大泽。未至，道渴而死。”

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.229.154]