Pro.ID21207 TitleNested Shrubbery Boxes Title链接http://10.20.2.8/oj/exercise/problem?problem_id=21207 AC0 Submit0 Ratio- 时间&空间限制描述After each commission to install a shrubbery, Roger the Shrubber has to transport many empty planting boxes with a drawn cart. In this instance, a planting box is a wooden box with one open side.
Given a set of n planting boxes, compute the largest number of boxes that can be nested. Specifically, report the number of the largest subset of boxes which may be nested such that the smallest box of the subset fits within the second smallest, the second smallest of the subset fits within the third smallest, the third smallest of the subset fits within the fourth smallest, and so forth.
A box i (bi) fits into box j (bj) if there exists some rotation of bi such that each dimension of bi is less than the corresponding dimension of bj. Any box can be rotated to nest inside another box. 输入The input will consist of an unspecified number of box sets. Each set will begin with a line containing n, 0 <= n <= 500, the number of boxes in the set. Each box will be described on its own line by three positive integers representing length, width and height (Each value will not exceed 1000). The first two numbers of each box description will be followed by a space, the letter ‘x’, and a space. The end of input occurs when n = -1. 输出Description After each commission to install a shrubbery, Roger the Shrubber has to transport many empty planting boxes with a drawn cart. In this instance, a planting box is a wooden box with one open side.
Given a set of n planting boxes, compute the largest number of boxes that can be nested. Specifically, report the number of the largest subset of boxes which may be nested such that the smallest box of the subset fits within the second smallest, the second smallest of the subset fits within the third smallest, the third smallest of the subset fits within the fourth smallest, and so forth.
A box i (bi) fits into box j (bj) if there exists some rotation of bi such that each dimension of bi is less than the corresponding dimension of bj. Any box can be rotated to nest inside another box. Input The input will consist of an unspecified number of box sets. Each set will begin with a line containing n, 0 <= n <= 500, the number of boxes in the set. Each box will be described on its own line by three positive integers representing length, width and height (Each value will not exceed 1000). The first two numbers of each box description will be followed by a space, the letter ‘x’, and a space. The end of input occurs when n = -1. Output For each set of boxes, print a line containing the largest number of boxes that can be selected from the original set to form a fully nesting subset of boxes. Sample Input 5
145 x 472 x 812
827 x 133 x 549
381 x 371 x 900
271 x 389 x 128
718 x 217 x 491
4
432 x 123 x 139
942 x 844 x 783
481 x 487 x 577
677 x 581 x 701
-1 Sample Output 2
4 Source 样例输入5
145 x 472 x 812
827 x 133 x 549
381 x 371 x 900
271 x 389 x 128
718 x 217 x 491
4
432 x 123 x 139
942 x 844 x 783
481 x 487 x 577
677 x 581 x 701
-1 样例输出2
4 作者 |
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2025-2-2 18:03 , Processed in 0.036244 second(s), 14 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
