2013
12-30

UVa OJ 103 – Stacking Boxes (嵌套盒子)

Time limit: 3.000 seconds

Background背景

Some concepts in Mathematics and Computer Science are simple in one or two dimensions but become more complex when extended to arbitrary dimensions. Consider solving differential equations in several dimensions and analyzing the topology of an n-dimensional hypercube. The former is much more complicated than its one dimensional relative while the latter bears a remarkable resemblance to its “lower-class” cousin.

The Problem问题

Consider an n-dimensional “box” given by its dimensions. In two dimensions the box (2,3) might represent a box with length 2 units and width 3 units. In three dimensions the box (4,8,9) can represent a box 4 × 8 × 9 (length, width, and height). In 6 dimensions it is, perhaps, unclear what the box (4,5,6,7,8,9) represents; but we can analyze properties of the box such as the sum of its dimensions.

In this problem you will analyze a property of a group of n-dimensional boxes. You are to determine the longest nesting string of boxes, that is a sequence of boxes b1, b2, …, bk such that each box bi nests in box bi+1 (1 ≤ i < k).

A box D = (d1, d2, …, dn) nests in a box E = (e1, e2, …, en) if there is some rearrangement of the di such that when rearranged each dimension is less than the corresponding dimension in box E. This loosely corresponds to turning box D to see if it will fit in box E. However, since any rearrangement suffices, box D can be contorted, not just turned (see examples below).

For example, the box D = (2,6) nests in the box E = (7,3) since D can be rearranged as (6,2) so that each dimension is less than the corresponding dimension in E. The box D = (9,5,7,3) does NOT nest in the box E = (2,10,6,8) since no rearrangement of D results in a box that satisfies the nesting property, but F = (9,5,7,1) does nest in box E since F can be rearranged as (1,9,5,7) which nests in E.

Formally, we define nesting as follows: box D = (d1, d2, …, dn) nests in box E = (e1, e2, …, en) if there is a permutation p of 1…n such that (dp(1), dp(2), …, dp(n)) “fits” in (e1, e2, …, en) i.e., if dp(i) < ei for all 1 ≤ i ≤ n.

The Input输入

The input consists of a series of box sequences. Each box sequence begins with a line consisting of the the number of boxes k in the sequence followed by the dimensionality of the boxes, n (on the same line.)

This line is followed by k lines, one line per box with the n measurements of each box on one line separated by one or more spaces. The ith line in the sequence (1 ≤ i ≤ k) gives the measurements for the ith box.

There may be several box sequences in the input file. Your program should process all of them and determine, for each sequence, which of the k boxes determine the longest nesting string and the length of that nesting string (the number of boxes in the string).

In this problem the maximum dimensionality is 10 and the minimum dimensionality is 1. The maximum number of boxes in a sequence is 30.

The Output输出

For each box sequence in the input file, output the length of the longest nesting string on one line followed on the next line by a list of the boxes that comprise this string in order. The “smallest” or “innermost” box of the nesting string should be listed first, the next box (if there is one) should be listed second, etc.

The boxes should be numbered according to the order in which they appeared in the input file (first box is box 1, etc.).

If there is more than one longest nesting string then any one of them can be 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

5
3 1 2 4 5
4
7 2 5 6

Solution解答

#include <algorithm>
#include <vector>
#include <functional>
#include <iostream>
using namespace std;
//盒子类
class BOX {
public:
//按文字顺序比较，用于对多个盒子进行排序
bool operator<=(const BOX& other) const {
return (lexicographical_compare(vecUnit.begin(), vecUnit.end(),
other.vecUnit.begin(), other.vecUnit.end()));
}
//判断是否可以嵌套，用于LIS算法
bool Contain(const BOX& other) const {
return (mismatch(vecUnit.begin(), vecUnit.end(),
other.vecUnit.begin(), greater<int>()).first == vecUnit.end());
}
//记录盒子的编号和维度
int nId; vector<int> vecUnit;
};
//主函数
int main(void) {
//循环处理每行输入数据
for (int nDemCnt, nBoxCnt; cin >> nBoxCnt >> nDemCnt;) {
vector<BOX> vecBoxes(nBoxCnt), aMat[30][30];
//循环输入每个盒子
for (int i = 0; i < nBoxCnt; i++) {
vecBoxes[i].nId = i;
vector<int> &vecUnit = vecBoxes[i].vecUnit;
//循环输入每个维度到盒子中
for (int j = 0, nUnit; j < nDemCnt; ++j) {
cin >> nUnit;
vecUnit.push_back(nUnit);
}
//并将盒子的维度值从大到小排序
sort(vecUnit.begin(), vecUnit.end(), greater<int>());
}
//按文字顺序从小到大排列所有盒子
sort(vecBoxes.begin(), vecBoxes.end(), less_equal<BOX>());
//vecMax记录以每个盒子为起始的最大嵌套长度
//vecPrev记录上一个盒子的位置
vector<int> vecMax(nBoxCnt, 0), vecPrev(nBoxCnt, -1);
//开始LIS算法
int nMax = 0;
vecMax.front() = 1;
for (int i = 1; i < nBoxCnt; ++i) {
for (int j = 0; j < i; ++j) {
//找出之前能嵌入当前盒子且拥有最大嵌套序列长度的盒子
if ((vecMax[j] > vecMax[i] || vecMax[i] == 0) &&
vecBoxes[i].Contain(vecBoxes[j])) {
//将最大嵌套序列长度更新到当前盒子
vecMax[i] = vecMax[j];
vecPrev[i] = j;
}
}
//当前盒子的最大嵌套序列长度要加上自身的1
if (++vecMax[i] > vecMax[nMax]) {
//找出所有盒子中的拥有最大嵌套序列的盒子
nMax = i;
}
}
//跟据vecPrev数组回溯，找出所有盒子
for (vecMax.clear(); nMax != -1; nMax = vecPrev[nMax]) {
vecMax.push_back(nMax);
}
//反转输出结果
vector<int>::reverse_iterator ri = vecMax.rbegin();
cout << vecMax.size() << '\n' << vecBoxes[*ri++].nId + 1;
for (; ri != vecMax.rend(); ++ri) {
cout << ' ' << vecBoxes[*ri].nId + 1;
}
cout << endl;
}
return 0;
}

1. 算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。