Preparing NOJ

嵌套箱问题

1000ms 65536K

Description:

一个d 维箱(x1,x2,….xd,)嵌入另一个d 维箱(y1,y2,….yd)是指存在1,2,,d 的一个排列π,使xn(1)<y1, xn(2)<y2,…, xn(d)<yd

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

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

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

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

Input:

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

Output:

程序运行结束时,对每个测试数据项,输出其最长嵌套箱序列的长度和从小到大排列的最长嵌套箱序列。

Sample Input:

5 2
3 7
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:

input.txt
5
3 1 2 4 5
4
7 2 5 6

Note:

undefined

本题由旧版NOJ导入,来源:NUAA

Info

NOJ

Provider NOJ

Code NOJ1262

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet