2013年8月11日

UVa 437 - The Tower of Babylon

#include <cstdio>
#include <vector>
#include <algorithm>
#define PB push_back
using namespace std;

struct Block {
  Block(int x, int y, int z) : x(x), y(y), z(z) {}
  bool operator>(const Block & other) const {
    return x < other.x && y < other.y;
  }
  bool operator<(const Block & other) const {
    return x != other.x ? x > other.x : y > other.y;
  }
  int x, y, z;
};

int main() {
  int n, C = 1;
  while (scanf("%d", &n) && n) {
    vector<Block> all;
    while (n--) {
      int x, y, z;
      scanf("%d%d%d", &x, &y, &z);
      all.PB(Block(x, y, z));
      all.PB(Block(x, z, y));
      all.PB(Block(y, x, z));
      all.PB(Block(y, z, x));
      all.PB(Block(z, x, y));
      all.PB(Block(z, y, x));
    }
    sort(all.begin(), all.end());
    int h[999] = {};
    for (int i = 0; i < all.size(); i++) {
      h[i] = all[i].z;
    }
    int max = 0;
    for (int i = 0; i < all.size(); i++) {
      for (int j = i + 1; j < all.size(); j++) {
        if (all[j] > all[i] && h[j] < h[i] + all[j].z) {
          h[j] = h[i] + all[j].z;
        }
      }
    }
    for (int i = 0; i < all.size(); i++) {
      max = h[i] > max ? h[i] : max;
    }
    printf("Case %d: maximum height = %d\n", C++, max);
  }
  return 0;
}

沒有留言:

張貼留言