【解題】Stacking Boxes

ACM Volume I 103 - Stacking Boxes


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 b₁, b₂, ..., b_k such that each box b_i nests in box b_{i + 1} (1 ≦ i ＜ k).

A box D = (d₁, d₂, ..., d_n) nests in a box E = (e₁, e₂, ..., e_n) if there is some rearrangement of the d_i 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 = (d₁, d₂, ..., d_n) nests in box E = (e₁, e₂, ..., e_n) if there is a permutation π of 1...n such that (d_π(1), d_π(2), ..., d_π(n)) ``fits'' in (e₁, e₂, ..., e_n) i.e., if d_π(i) < e_i 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 i^th line in the sequence (1 ≦ i ≦ k) gives the measurements for the i^th 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


Sample Output

5
3 1 2 4 5
4
7 2 5 6


解題思考

　　首先，看到問題描述，我們需要判斷一個盒子能不能"放入"另一個盒子中。也就是說，兩種序列組合d, e的某一種重排，能使得 d_i > e_i 恆成立。由於我們不想花時間去不斷重排、測試，因此在測試前我們先統一將序列內容從小排到大(或是從大排到小也行)。

　　接著，再使用一個 boolean 陣列 nest[i][j]，判別序列 j 是否可以"放入"序列 i 之中。至於怎麼判斷，由於序列都是相同的由小排到大(或由大排到小)，因此直接用迴圈去一一比對即可。

　　最後，就是分別選擇不同的盒子當最外層，使用遞迴的方式。每遞迴一層就相當於在盒子最內層再"塞"進一個盒子。接著只要找出能套入最多盒子的組合，並把組合的串列輸出出來，就達成題目的要求了。


參考解答(C++)

#include <iostream>

using namespace std;

int compare(const void *, const void *);
bool stack(int);

int maxn, k, n, **box, *list, num;
bool **nest;

int main(void)
{
    while (cin >> k)
    {
        cin >> n;

        maxn = num = 0;

        // 動態配置記憶體
        list = new int[k];

        box = new int *[k];
        for (int i = 0; i < k; i++)
        {
            box[i] = new int[n];
            for (int j = 0; j < n; j++)
            {
                cin >> box[i][j];
            }

            // 將內容從小排到大
            qsort(box[i], n, sizeof(int), compare);
        }

        nest = new bool *[k];
        for (int i = 0; i < k; i++)
        {
            // 設定 i 是否可容納 j 的布林變數
            nest[i] = new bool[k];
            for (int j = 0; j < k; j++)
            {
                if (i == j)
                {
                    nest[i][j] = false;
                    continue;
                }

                nest[i][j] = true;
                for (int t = 0; t < n; t++)
                {
                    if (box[i][t] >= box[j][t])
                    {
                        nest[i][j] = false;
                        break;
                    }
                }
            }
        }

        // 呼叫遞迴函式
        for (int i = 0; i < k; i++)
        {
            if (stack(i)) { list[0] = i; }
        }

        // 輸出執行結果
        cout << maxn << endl;
        for (int i = 0; i < maxn; i++)
        {
            cout << list[i] + 1;

            if (i < maxn - 1) { cout << " "; }
            else { cout << endl; }
        }

        // 釋放記憶體空間
        delete [] list;

        for (int i = 0; i < k; i++) { delete [] box[i]; }
        delete [] box;

        for (int i = 0; i < k; i++) { delete [] nest[i]; }
        delete [] nest;
    }

#ifndef ONLINE_JUDGE
    system("pause");
#endif
}

int compare(const void *a, const void *b)
{
    int *arg1 = (int *)a;
    int *arg2 = (int *)b;

    if(*arg1 < *arg2)       { return -1; }
    else if(*arg1 == *arg2) { return 0; }
    else                    { return 1; }
}

bool stack(int now)
{
    bool ok = false;

    num++;
    for (int i = 0; i < k; i++)
    {
        // 假如可以 i 放入 now
        if (nest[now][i])
        {
            nest[now][i] = false;

            if (stack(i))
            {
                list[num] = i;
                ok = true;
            }

            nest[now][i] = true;
        }
    }

    num--;

    // 得到最長套入串列長度
    if (num + 1 > maxn)
    {
        maxn = num + 1;
        return true;
    }

    return ok;
}