和之前的 Stacking Boxes 很像，但是这里求的是最大高度，并且盒子成了立体状，因此对每个盒子有三种不同的高度，分别为x, y, z，相当于增加两个盒子；

记忆化搜索。

1 # include 
     
        2 # include 
      
         3  4 typedef struct {
    5     int x;  6     int y;  7     int h;  8 }block;  9 10 int n; 11 int f[91]; 12 block b[91]; 13 14 int cmp(const void *x, const void *y) 15 {
   16     return (*(int *)x > *(int *)y ? 1:-1); 17 } 18 19 int dp(int i); 20 21 int main() 22 {
   23     int i, cnt, maxH, tmp, t[3]; 24 25     cnt = 0; 26     while (1) 27     {
   28         ++cnt; 29         scanf("%d", &n); 30         if ( !n ) break; 31         n *= 3; 32         for ( i = 1; i <= n; ++i) 33         {
   34             scanf("%d%d%d", &t[0], &t[1], &t[2]); 35             qsort(t, 3, sizeof(int), cmp); 36             b[i].x = t[0]; b[i].y = t[1]; b[i].h = t[2]; ++i; 37             b[i].x = t[0]; b[i].y = t[2]; b[i].h = t[1]; ++i; 38             b[i].x = t[1]; b[i].y = t[2]; b[i].h = t[0]; 39         } 40 41         maxH = 0; 42         memset(f, 0, sizeof(f)); 43         for ( i = 1; i <= n; ++i) 44             if (maxH < (tmp = dp(i))) maxH = tmp; 45         46         printf("Case %d: maximum height = %d\n", cnt, maxH); 47     } 48 49     return 0; 50 } 51 52 int dp(int i) 53 {
   54     int j, tmp; 55     56     if (f[i] > 0) return f[i]; 57     f[i] = b[i].h; 58     for ( j = 1; j <= n; ++j) 59     {
   60         if (b[i].x>b[j].x && b[i].y>b[j].y && f[i] < (tmp = dp(j)+b[i].h)) 61             f[i] = tmp; 62        } 63         64     return f[i]; 65 }