题目描述
一个d 维箱(x1，x2，……，xd ) 嵌入另一个d 维箱(y1，y2，……，yd) 是指存在1,2,…,d 的一个排列π，使得 xπ1 < y1 , xπ2 < y2 ,…, xπ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≤50），分别表示箱的个数和维数。其后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
参考代码
暂无
解析
暂无
