UVa 437 - The Tower of Babylon

Contents

1. 1. Problem
2. 2. Solution
3. 3. Code

Problem

中文網址

Solution

積木可隨意旋轉，先將長寬高排序好後，可以歸納出 3 種可能:
(以 1 2 3 表其相對大小)

長 寬 高
1 2 3
1 3 2
2 3 1

當然也可以直接存其 6 種組合。

接著排序所有積木，要可以疊在上面它的長和寬必定小於下面的長和寬，所以可先用:

bool operator<(const Block& b)
{
    if (len[0] == b.len[0])
        return len[1] < b.len[1];
    else
        return len[0] < b.len[0];
}

排出先後關係。

最後再做 LIS 時用條件判斷即可:

if (blocks[i].len[0] < blocks[j].len[0] && blocks[i].len[1] < blocks[j].len[1])
    hight[j] = max(hight[j], hight[i] + blocks[j].len[2]);

Code

UVa 437

#include<cstdio>
#include<algorithm>
#define N 30*3
using namespace std;

struct Block
{
    int len[3];

    bool operator<(const Block& b)
    {
        if (len[0] == b.len[0])
            return len[1] < b.len[1];
        else
            return len[0] < b.len[0];
    }

}blocks[N];
int main()
{
    int n, Case = 1, hight[N];
    while (scanf("%d", &n) && n)
    {
        int i, j;
        n *= 3;

        for (i = 0; i < n; i++)
        {
            int dim[3];
            scanf("%d%d%d", &dim[0], &dim[1], &dim[2]);
            sort(dim, dim + 3);

            blocks[i].len[0] = dim[0], blocks[i].len[1] = dim[1], blocks[i].len[2] = dim[2];//0,1,2
            i++;
            blocks[i].len[0] = dim[0], blocks[i].len[1] = dim[2], blocks[i].len[2] = dim[1];//0,2,1
            i++;
            blocks[i].len[0] = dim[1], blocks[i].len[1] = dim[2], blocks[i].len[2] = dim[0];//1,2,0
        }

        sort(blocks, blocks + n);

        for (i = 0; i < n; i++)
            hight[i] = blocks[i].len[2];

        for (i = 0; i < n; i++)
            for (j = i + 1; j < n; j++)
                if (blocks[i].len[0] < blocks[j].len[0] && blocks[i].len[1] < blocks[j].len[1])
                    hight[j] = max(hight[j], hight[i] + blocks[j].len[2]);

        int max = -1;
        for (i = 0; i < n; i++)
            if (max < hight[i])
                max = hight[i];

        printf("Case %d: maximum height = %d\n", Case++, max);
    }

    return 0;
}