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

上一题 正确率: $0.00\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $1$ 正确数量 $0$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 贪心

Description

一个 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 维箱中的一个最长嵌套箱序列。

Input

输入包含多个测试数据项。每个测试数据项的第一行中有2 个整数 n 和 d，分别表示箱的个数和维数。其后 n 行每行有 d 个正整数，表示箱的各维的长度。

Output

对每个测试数据项，输出其最长嵌套箱序列的长度和从小到大排列的最长嵌套箱序列。

Sample Input复制

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

Sample Output复制

5
3 1 2 4 5 
4
7 2 5 6