Pro.ID21160 TitleThe Bale Tower Title链接http://10.20.2.8/oj/exercise/problem?problem_id=21160 AC27 Submit174 Ratio15.52% 时间&空间限制描述Always bored with cud-chewing, the cows have invented a new game. One cow retrieves a set of N (3 ≤ N ≤ 20) hay bales from the shed each of which is one unit high. Each bale also has some unique width and unique breadth. A second cow tries to choose a set of bales to make the tallest stack of bales in which each bale can be placed only on a bale whose own width and breadth are smaller than the width and breadth of the bale below. Bales can not be rotated to interchange the width and breadth. Help the cows determine the highest achievable tower that can be legally built form a set of bales. 输入Multiple test case. For each case: * Line 1: A single integer, N * Lines 2..N+1: Each line describes a bale with two space-separated integers, respectively the width and breadth 输出Description Always bored with cud-chewing, the cows have invented a new game. One cow retrieves a set of N (3 ≤ N ≤ 20) hay bales from the shed each of which is one unit high. Each bale also has some unique width and unique breadth. A second cow tries to choose a set of bales to make the tallest stack of bales in which each bale can be placed only on a bale whose own width and breadth are smaller than the width and breadth of the bale below. Bales can not be rotated to interchange the width and breadth. Help the cows determine the highest achievable tower that can be legally built form a set of bales. Input Multiple test case. For each case: * Line 1: A single integer, N * Lines 2..N+1: Each line describes a bale with two space-separated integers, respectively the width and breadth Output For each case, output one line: The height of the tallest possible tower that can legally be built from the bales. Sample Input 6 Sample Output 5 Hint Input Details Six bales of various widths and breadths Output Details These bales can be stacked for a total height of 5: 10 12 [another stacking exists, too] Source 样例输入6 样例输出5 提示Input Details Six bales of various widths and breadths Output Details These bales can be stacked for a total height of 5: 10 12 [another stacking exists, too] |