Problem E: 算法实现题 4-14 嵌套箱问题(习题 4-31)

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $1$ 正确数量 $0$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 贪心
一个 d 维箱(x1 , x2 ,  , xd ) 嵌入另一个 d 维箱(y1 , y2 ,  , yd ) 是指存在 1,2,…,d 的一个排列q,使得 xq (1) < y1 , xq(2) < y2 ,…, xq (d ) < yd 。
(1)证明上述箱嵌套关系具有传递性;
(2)试设计一个有效算法,用于确定一个 d 维箱是否可嵌入另一个 d 维箱;
(3)给定由 n 个 d 维箱组成的集合{B1 , B2 , , Bn },试设计一个有效算法找出这 n 个 d
维箱中的一个最长嵌套箱序列,并用 n 和 d 描述算法的计算时间复杂性。
算法设计:
给定由 n 个 d 维箱,试设计一个有效算法,找出这 n 个 d 维箱中的一个最长嵌套箱序列。

输入包含多个测试数据项。每个测试数据项的第一行中有2 个整数 n 和 d,分别表示箱的个数和维数。其后 n 行每行有 d 个正整数,表示箱的各维的长度。
对每个测试数据项,输出其最长嵌套箱序列的长度和从小到大排列的最长嵌套箱序列。
5 2
3 7
8 10
5 2
9 11
21 18
8 6
5 2 20 1 30 10
23 15 7 9 11 3
40 50 34 24 14 4
9 10 11 12 13 14
31 4 18 8 27 17
44 32 13 19 41 19
1 2 3 4 5 6
80 37 47 18 21 9
5
3 1 2 4 5 
4
7 2 5 6