UVA - 437 The Tower of Babylon

Intuition

Contruct a tower of Babylon use Blocks.
Since Blocks can be flip, we got 6 different cases with one type of block.
Put them into a vector, sort them, and it’s a simple LIS problem.

p.s. One difference from typical LIS problem is that it’s wants maximum height.

Example Code :

#include <bits/stdc++.h>
using namespace std;

#define mpb(x, y, z) v.push_back({x, y, z})

int main()
{
    int tt = 0;
    int n;
    while (cin >> n && n)
    {
        vector<vector<int>> v;
        for (int i = 0; i < n; i++)
        {
            int x, y, z;
            cin >> x >> y >> z;
            mpb(x, y, z);
            mpb(x, z, y);
            mpb(y, x, z);
            mpb(y, z, x);
            mpb(z, x, y);
            mpb(z, y, x);
        }
        sort(v.begin(), v.end());
        vector<int> dp(v.size() + 1, 0);
        for (int i = 0; i < v.size(); i++)
        {
            dp[i] = v[i][2];
            for (int j = 0; j < i; j++)
            {
                if (v[i][0] > v[j][0] && v[i][1] > v[j][1])
                    dp[i] = max(dp[i], dp[j] + v[i][2]);
            }
        }
        int res = *max_element(dp.begin(), dp.end());
        cout << "Case " << ++tt << ": maximum height = " << res << "\n";
    }
}