uva 437 - The Tower of Babylon

/*

Problem link

This problem can be attacked in many solution. I choose the DP solution.

It is a bit similar to the LIS.

Algorithm: 

There are 3 states of 1 block:

  state 1: x,y are chosen as the base;

  state 2: x,z are chosen as the base;

  state 3: y,z are chosen as the base;

- Let d[i][j] is the highest height if block i at state j when block i is on top

of the building.

- We optimize d[i][j] by looking for the block ii at state jj which block i can

be place on it and update the height of the tower if it gets taller.Hence:

  d[i][j] = max(d[i][j], d[ii][jj] + height(a[i],j)) for ii from 1 to n and jj

  from 1 to 3;

- But each block can be used several times (at most 3 times). Therefore we repeat

the whole procedure until d[i][j] is optimized, that is, d[i][j] remains

unchanged after the procedure.

- The complexity for this algorithm in the worst case is O(n^3*9). But usually, 

it will take O(n^2*9*k) where k is the total number of blocks of the 

highest tower. 

*/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
using namespace std;
const int maxn = 34;
//----------------------------
class block {public: int x; int y; int z;};
struct trace {
 int x; 
 int y;
};
//----------------------------
block a[maxn];
int d[maxn][4],tmp[maxn][4];
trace tr[maxn][4];
int n;
//----------------------------
bool readfile() {
 cin >> n;
 if (n==0) return(false);
 for (int i=1; i<=n; i++) cin >> a[i].x >> a[i].y >> a[i].z;
 return(true);
}
//----------------------------
// The ok() function check whether block a1 at state1 can be place on block a2 at state2
// Note that a1 at state1 can be rotate 90 degree...
bool ok(block a1, block a2, int state1, int state2) {
 if (state1==1 && state2==1) 
  return((a2.x>a1.x && a2.y>a1.y) || (a2.x>a1.y && a2.y>a1.x));
 if (state1==1 && state2==2) 
  return((a2.x>a1.x && a2.z>a1.y) || (a2.x>a1.y && a2.z>a1.x));
 if (state1==1 && state2==3) 
  return((a2.y>a1.x && a2.z>a1.y) || (a2.y>a1.y && a2.z>a1.x));
 if (state1==2 && state2==1) 
  return((a2.x>a1.x && a2.y>a1.z) || (a2.x>a1.z && a2.y>a1.x));
 if (state1==2 && state2==2) 
  return((a2.x>a1.x && a2.z>a1.z) || (a2.x>a1.z && a2.z>a1.x));
 if (state1==2 && state2==3) 
  return((a2.y>a1.x && a2.z>a1.z) || (a2.y>a1.z && a2.z>a1.x));
 if (state1==3 && state2==1) 
  return((a2.x>a1.y && a2.y>a1.z) || (a2.x>a1.z && a2.y>a1.y));
 if (state1==3 && state2==2) 
  return((a2.x>a1.y && a2.z>a1.z) || (a2.x>a1.z && a2.z>a1.y));
 if (state1==3 && state2==3) 
  return((a2.y>a1.y && a2.z>a1.z) || (a2.y>a1.z && a2.z>a1.y));
}
//----------------------------
// The function height() return the height of block a1 at state1
int height(block a1, int state1) {
 switch (state1)
 {
  case 1: {
   return(a1.z);
   break;
  }
  case 2: {
   return(a1.y);
   break;
  }
  case 3: {
   return(a1.x);
   break;
  }
 }
}
//----------------------------
int solve() {
 int result = 0;
 // At first block i is its height at state j
 for (int i=1; i<=n; i++) 
  for (int j=1; j<=3; j++)
  {
   d[i][j] = height(a[i],j);
   tr[i][j].x = i;
   tr[i][j].y = j;
   result = max(result,d[i][j]);
  }
 bool flag;
 do
 { 
  // Save the current table of solutions
  for (int i=1; i<=n; i++)
   for (int j=1; j<=3; j++) tmp[i][j] = d[i][j];
  
  /*
  For each block i at state j, check if it can be place on top of 
  block ii at state jj. If it does, update its height.
  */ 
  for (int i=1; i<=n; i++)
   for (int j=1; j<=3; j++)
   {
    for (int ii=1; ii<=n; ii++)
     for (int jj=1; jj<=3; jj++)
      if (ok(a[i],a[ii],j,jj) 
       && d[i][j]<d[ii][jj]+height(a[i],j))
      {
       d[i][j] = d[ii][jj]+height(a[i],j);
       tr[i][j].x = ii;
       tr[i][j].y = jj;
      }
    if (d[i][j]>result) result = d[i][j];
   }
  
  // Check if the solutions table have been changed or not?
  // If not, then this is the optimize solution
  flag  = false;
  for (int i=1; i<=n; i++)
   for (int j=1; j<=3; j++) 
    if (d[i][j]!=tmp[i][j]) 
    {
     flag = true;
     break;
    }
 } while (flag);
 return(result);
}
//----------------------------
int main() {
 int test = 0;
 while (readfile())
 {
  test++;
  printf("Case %d: maximum height = ",test); 
  cout << solve() << endl;
 }
 return 0;
}
//----------------------------