runtah

UVa 437 The Tower of Babylon

UVa 437 The Tower of Babylon

Method: LIS (Modified)
You can only see the problem as an LIS Problem but you cannot solve it using LIS principles. All the six sides of the blocks have to be considered. If you test them using the rotational if in the LIS algorithm, they are just testing one or two but all the sides. So you have to make the list with six sides. -Thanks to Rakib (My team mate for contests) for pointing this out :) Code:

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>

typedef int lint;

using namespace std;

typedef struct blk {
 int x, y, z; 
} block;


bool comp( block a, block b ) {
 if (a.x != b.x) return (a.x<b.x);
 else if (a.y!=b.y) return (a.y<b.y); 
 else return (a.z<b.z);
}

vector<block> lst;
int lis[1000];

int LIS( int n ) {

 int max_lis(-1), i, j, k;
 
 for (int i=0 ; i<n ; i++) {
 lis[i] = lst[i].z;
 for (int j=0 ; j<i ; j++) {
 if (( (lst[i].x > lst[j].x && lst[i].y > lst[j].y) || (lst[i].x > lst[j].y && lst[i].y > lst[j].x) ) ) {
 lis[i] = max ( lis[i] , lis[j]+lst[i].z );
 }
 }
 max_lis = max ( lis[i] , max_lis );
 }
 return max_lis;
}

int main( void ) {

 int n, i, x, y, z, kase=1;

 while ( scanf("%d",&n) && n ) {
 
 lst.clear();
 
 for (i=0 ; i<n ; i++) {
 scanf("%d %d %d",&x,&y,&z);
 
 lst.push_back( (block) {x,y,z} );
 lst.push_back( (block) {x,z,y} );
 lst.push_back( (block) {y,x,z} );
 lst.push_back( (block) {y,z,x} );
 lst.push_back( (block) {z,x,y} );
 lst.push_back( (block) {z,y,x} );
 }
 
 sort(lst.begin(), lst.end(), comp);
 
 int res = LIS( lst.size() );
 
 printf("Case %d: maximum height = %d ",kase++,res);
 } 
 return 0;
}

Go to link download