UVa 437 (变形的LIS) The Tower of Babylon

题意：

有n种类型的长方体，每种长方体的个数都有无限个。当一个长方体的长和宽分别严格小于另一个长方体的长和宽的时候，才可以把这个放到第二个上面去。输出这n种长方体能组成的最大长度。

分析：

虽说每种都有无限个，可每种长方体一共的“姿态”最多也只有三种，将它们三个边长分别作为高。然后按照底面排序，就转化为最大上升子列的问题。

代码中采用了“人人为我”的方法。

 //#define LOCAL

 #include <iostream>

 #include <algorithm>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 const int maxn = ;

 struct Cube

 {

     int x, y, z;

     bool operator< (const Cube& a) const

     { return x < a.x || (x == a.x && y < a.y); }

 }cubes[maxn];

 int size[], dp[maxn];

 bool check(int a, int b)

 {

     return (cubes[a].x < cubes[b].x && cubes[a].y < cubes[b].y);

 }

 int main(void)

 {

     #ifdef LOCAL

         freopen("437in.txt", "r", stdin);

     #endif

     int n, kase = ;

     while(scanf("%d",&n) ==  && n)

     {

         for(int i = ; i < n; ++i)

         {

             for(int j = ; j < ; ++j)    scanf("%d", &size[j]);

             sort(size, size + );

             cubes[i*].x = size[], cubes[i*].y = size[], cubes[i*].z = size[];

             cubes[i*+].x = size[], cubes[i*+].y = size[], cubes[i*+].z = size[];

             cubes[i*+].x = size[], cubes[i*+].y = size[], cubes[i*+].z = size[];

         }

         n *= ;

         sort(cubes, cubes + n);

         memset(dp, , sizeof(dp));

         for(int i = ; i < n; ++i)    dp[i] = cubes[i].z;

         for(int i = ; i < n; ++i)

             for(int j = ; j < i; ++j)

                 if(check(j, i))    dp[i] = max(dp[i], cubes[i].z + dp[j]);

         int ans = ;

         for(int i = ; i < n; ++i)    ans = max(ans, dp[i]);

         printf("Case %d: maximum height = %d\n", ++kase, ans);

     }

     return ;

 }

代码君