神马品牌网荒野行动警告危险区域:第四题 箱子嵌套
来源：百度文库 编辑：神马品牌网 时间：2024/05/05 00:48:43
【问题描述】
考虑一个给出为N维空间“箱子”的尺度问题。当有两个尺度时，箱子（2，3）表示这个箱子长度为2个单位，宽度为3个单位。当有三个尺度时，箱子（4，8，9）表示这个箱子长度是4个单位，宽度是8个单位，高度是9个单位。当它有6个尺度时，也许，它表现的是不易了解的箱子（4，5，6，7，8，9）；但是我们能分析这个箱子的特性，例如它的各个尺度。
在这个问题中你将分析许多关于N维空间的箱子，并解决这些箱子的最大的嵌套问题。箱子D =（d1,d2,…,dn），箱子E = （e1,e2,…,en），di和ei都可以重新排列整理，那么当它们重新排列整理后，箱子D所有的尺度都小于箱子E所有的尺度，那么箱子D可以放入箱子E中。
例如，箱子D =（2，6），当D重新排列整理成（6，2），则可放入箱子E =（7，3）中，此时D每个尺度都小于E的相应尺度。如果D经过重新整理后D =（9，7，5，3），则不可以放入箱子E =（10，8，6，2）中，但是F =（9，5，7，1），重新整理后F =（9，7，5，1），即符合F放入E的条件。
【输入文件】
输入文件boxes.in中，第一行有两个整数，第一个整数为箱子的总数K，第二个整数为每个箱子的空间维数N。以下K行，每行表示一个箱子，有N个尺度数据，数据间用一个或数个空格分开。（K ≤ 10000，N ≤ 10）
【输出文件】
输出文件Boxes.out仅包含一个整数，输出最大箱子嵌套数目。
【样例数据】
BOXES.IN
5 2
3 7
8 10
5 2
9 11
21 18
BOXES.OUT
5
考虑一个给出为N维空间“箱子”的尺度问题。当有两个尺度时，箱子（2，3）表示这个箱子长度为2个单位，宽度为3个单位。当有三个尺度时，箱子（4，8，9）表示这个箱子长度是4个单位，宽度是8个单位，高度是9个单位。当它有6个尺度时，也许，它表现的是不易了解的箱子（4，5，6，7，8，9）；但是我们能分析这个箱子的特性，例如它的各个尺度。
在这个问题中你将分析许多关于N维空间的箱子，并解决这些箱子的最大的嵌套问题。箱子D =（d1,d2,…,dn），箱子E = （e1,e2,…,en），di和ei都可以重新排列整理，那么当它们重新排列整理后，箱子D所有的尺度都小于箱子E所有的尺度，那么箱子D可以放入箱子E中。
例如，箱子D =（2，6），当D重新排列整理成（6，2），则可放入箱子E =（7，3）中，此时D每个尺度都小于E的相应尺度。如果D经过重新整理后D =（9，7，5，3），则不可以放入箱子E =（10，8，6，2）中，但是F =（9，5，7，1），重新整理后F =（9，7，5，1），即符合F放入E的条件。
【输入文件】
输入文件boxes.in中，第一行有两个整数，第一个整数为箱子的总数K，第二个整数为每个箱子的空间维数N。以下K行，每行表示一个箱子，有N个尺度数据，数据间用一个或数个空格分开。（K ≤ 10000，N ≤ 10）
【输出文件】
输出文件Boxes.out仅包含一个整数，输出最大箱子嵌套数目。
【样例数据】
BOXES.IN
5 2
3 7
8 10
5 2
9 11
21 18
BOXES.OUT
5
说一下思路吧~~~
先把每个箱子的尺度从大到小排一个序，然后如果一个箱子的每个尺度都分别大于另一个箱子的相应尺度，那么这两个箱子就可以嵌套。
然后用两个循环根据两个箱子是否能嵌套生成一个有向图，用邻接矩阵表示，然后分别以每个顶点为根结点进行深度优先搜索，得到的最大深度就是最大箱子嵌套数目了~~~