同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

2051_嵌套箱问题

2022-5-16 18:18| 发布者: Hocassian| 查看: 52| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-3-89504278917800-Problem List-采集的数据-后羿采集器.html

Pro.ID

2051

Title

嵌套箱问题

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=2051

AC

Submit

Ratio

12.50%

时间&空间限制

Time Limit: 1000/500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

描述

一个d维箱( x₁, x₂, ... , x_d) 嵌入另一个d维箱( y₁, y₂, ..., y_d ) 是指存在1, 2, …, d的一个排列 π ，使得

(1) 证明上述箱嵌套关系具有传递性；

(2) 试设计一个有效算法，用于确定一个d维箱是否可嵌入另一个d维箱；

(3) 给定由n个d维箱组成的集合{ B₁, B₂, ..., B_n } ，试设计一个有效算法找出这n个d维箱中的一个最长嵌套箱序列，并用n和d描述算法的计算时间复杂性。

给定由n个d维箱，试设计一个有效算法，找出这n个d维箱中的一个最长嵌套箱序列。

输入

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

输出

Description

一个d维箱( x₁, x₂, ... , x_d) 嵌入另一个d维箱( y₁, y₂, ..., y_d ) 是指存在1, 2, …, d的一个排列 π ，使得

(1) 证明上述箱嵌套关系具有传递性；

(2) 试设计一个有效算法，用于确定一个d维箱是否可嵌入另一个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

Sample Output

5
3 1 2 4 5
4
7 2 5 6

Author

John

样例输入