UVa 437 : The Tower of Babylon

問題リンク：The Tower of Babylon

問題概要：
x*y*zの長方形がn個（nは30以下）与えられる
以下の条件を満たすとき長方形を別の長方形に載せることができる
条件：長方形の上にのせる長方形の横と縦の長さは下の長方形の横と縦の長さ未満でないといけない

この時、長方形をうまく積み重ねたとき最大どこまで高く積むことができるか？

解法：
長方形の置き方次第で高さが変わるので、その全てを記録しておく
x y z の中から2辺をきめて縦と横とする
この時選ばれなかった辺が高さとなる
あとはこれをグラフに落としてDPをすれば答えが出る
上の条件を満たしているならば辺をはる
これはDAGになる
縦 >= 横 という条件を付ければ普通にソートするだけでトポロジカルソートしたものと同様の効果を得られる

//初期化
for i 0..(長方形の数)
  dp[i] = (長方形の高さ)

//DP
for i 0..(長方形の数)
  for j i..(長方形の数)
    dp[i] = max(dp[i],dp[j] + (長方形jの高さ))

このdp配列の中で最大の値が答えとなる

コード:

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<set>
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define inf (1<<29)
#define MAX 100
using namespace std;
struct Point
{
  int x,y,cost;
  Point(int x=-inf,int y=-inf,int cost=-inf):x(x),y(y),cost(cost){}
  bool operator < (const Point& a)const
  {
    if(x != a.x)return x > a.x;
    return y > a.y;
  }
};
 
struct P
{
  int to,cost;
  P(int to=-inf,int cost=-inf):to(to),cost(cost){}
};
 
template<typename T>
bool visit(const T& G,int v,vector<int>& order,vector<int>& color)
{
  color[v] = 1;
  for(__typeof((G[v]).begin()) e = G[v].begin();e != G[v].end();e++)
    {
      if(color[e->to] == 2)continue;
      if(color[e->to] == 1)return false;
      if(!visit(G,e->to,order,color))return false;
    }
  order.push_back(v);
  color[v] = 2;
  return true;
}
 
template<typename T>
bool topologicalSort(const T& G,vector<int>& order)
{
  int SizeG = G.size();
  vector<int> color(SizeG); 
  for(int u=0;u<SizeG;u++)
    if(!color[u] && !visit(G,u,order,color))
      return false;
  reverse(order.begin(),order.end());
  return true;
}
 
 
vector<vector<P> > G;
int N;
int dp[MAX];
 
int main()
{
  int n,CNT = 1;
  while(cin >> n,n)
    {
      vector<Point> vec;
      {
    set<Point> tmp;
    int x,y,z;
    rep(i,n)
      {
        cin >> x >> y >> z;
        tmp.insert(Point(max(x,y),min(x,y),z));
        tmp.insert(Point(max(x,z),min(x,z),y));
        tmp.insert(Point(max(y,z),min(y,z),x));
      }
    for(set<Point>::iterator it = tmp.begin(); it != tmp.end(); it++)
      vec.push_back(*it);
      }
 
      N = vec.size();
      G.clear();
      G.resize(N,vector<P>());
      rep(i,N)rep(j,N)if(vec[i].x > vec[j].x && vec[i].y > vec[j].y)G[i].push_back(P(j,vec[j].cost));
 
      
      int mexico = 0;
      vector<int> order;
      topologicalSort(G,order);
      rep(i,N)dp[i] = vec[i].cost,mexico = max(mexico,dp[i]);
      rep(i,N)
    {
      int cur = order[i];
      rep(j,G[cur].size())
        {
          int to = G[cur][j].to;
          dp[to] = max(dp[to],dp[cur] + G[cur][j].cost);
          mexico = max(mexico,dp[to]);
        }
    }
      cout << "Case " << CNT++ << ": maximum height = " << mexico << endl;
 
    }
  return 0;
}