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
(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
such that each box 
nests in box 
( 
.A box D = (
) nests in a box E = ( 
) if there is some rearrangement of the 
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 = (
) nests in box E = ( ) if there is a permutation 
of 
such that ( 
) ``fits'' in ( ) i.e., if 
for all 
.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
line in the sequence ( 
) gives the measurements for the 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 kboxes 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
Sample Output
5 3 1 2 4 5 4 7 2 5 6
出處: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=39
問題描述
此問題首先會給您盒子的數量，並且告訴您盒子的維度(會超過三維)，接著會輸入每一個盒子的邊長，最後要您求出最多可以疊多少個盒子，並且印出疊最多盒子的串列。
解題思路
首先如何判斷盒子A是否可以塞進盒子B裡呢? 根據題目的定義，只要盒子A有任何一種邊長的排列方式可以使得盒子A所有的邊長都比盒子B的邊長來得小，就可以將盒子A塞進盒子B裡。最直接的判斷方法就是把所有盒子的邊長都先排序好，最後只需要從第一個邊長逐一比較到最後一個邊長，若盒子A的每個邊長皆比盒子B來得小，那就表示盒子A可以塞進盒子B裡，否則就不行。至於如何找出可以疊最多盒子的串列呢? 其實此問題可以用dynamic programming的方法來解，也就是使用類floyd-warshall的演算法，把每個盒子視為一個點，把可以疊的盒子數量視為路徑長，最後只需把求最短路徑改成求最長路徑即可。
c++程式碼
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void findPath(vector< vector<int> >& path, int startVertex, int endVertex) {
if (path[startVertex][endVertex] != -1) {
findPath(path, startVertex, path[startVertex][endVertex]);
cout << " " << path[startVertex][endVertex] + 1;
findPath(path, path[startVertex][endVertex], endVertex);
}
}
int main() {
int boxNum, dimens;
while (cin >> boxNum >> dimens) {
vector< vector<int> > boxes(boxNum, vector<int>(dimens, 0));
vector< vector<int> > pathLength(boxNum, vector<int>(boxNum, 0));
vector< vector<int> > path(boxNum, vector<int>(boxNum, -1));
int maxPathLength = -1;
int startVertex = -1;
int endVertex = -1;
for (int i=0; i<boxes.size(); i++) {
for (int j=0; j<boxes[i].size(); j++)
cin >> boxes[i][j];
sort(boxes[i].begin(), boxes[i].end());
}
for (int i=0; i<boxes.size(); i++) {
for (int j=0; j<boxes.size(); j++) {
bool isNest = true;
for (int k=0; k<boxes[i].size(); k++) {
if (boxes[i][k] >= boxes[j][k]) {
isNest = false;
break;
}
}
if (isNest)
pathLength[i][j] = 1;
if (pathLength[i][j] > maxPathLength) {
maxPathLength = pathLength[i][j];
startVertex = i;
endVertex = j;
}
}
}
for (int k=0; k<boxes.size(); k++) {
for (int i=0; i<boxes.size(); i++) {
for (int j=0; j<boxes.size(); j++) {
if (pathLength[i][k] != 0 && pathLength[k][j] != 0 && pathLength[i][k] + pathLength[k][j] > pathLength[i][j]) {
pathLength[i][j] = pathLength[i][k] + pathLength[k][j];
path[i][j] = k;
if (pathLength[i][j] > maxPathLength) {
maxPathLength = pathLength[i][j];
startVertex = i;
endVertex = j;
}
}
}
}
}
cout << maxPathLength + 1 << endl;
cout << startVertex + 1;
if (maxPathLength) {
findPath(path, startVertex, endVertex);
cout << " " << endVertex + 1 << endl;
}
else
cout << endl;
}
return 0;
}
沒有留言:
張貼留言