Contents

1. 1. 题目大意：
2. 2. 分析：

题目大意：

　　现有不超过三十个的立方体。给定其边长：abc。已知每种立方体的个数不限。现在欲堆放立方体，两个立方体能够堆叠的条件是上面的立方体的底面长和宽严格小于放在其下面的立方体。问由这些立方体最高能够堆叠多高。

分析：

• 因为立方体的个数不限，所以输入的时候只保存使x < y的三种情况(看代码)
• 按x从小到大排个序，接下来类似按最长上升子序列的问题，假设第i个为x，y相对来说最大的一个，找出符合x < d[i].x, y < d[i].y的最大h和

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1010;

struct node{
    int x;
    int y;
    int h;
}arr[N];

int dp[1010], n;

int cmp(node a, node b){
    if(a.x < b.x){
            return 1;
    }
    return 0;
}

int main(){

    freopen("input.txt", "r", stdin);
    int cas=1;
    while(scanf("%d", &n) && n) {
        int cur = 0;
        for(int i = 0; i < n; i++)   {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            arr[cur].x = min(a, b),  arr[cur].y = max(a, b),  arr[cur++].h = c;
            arr[cur].x = min(a, c),  arr[cur].y = max(a, c),  arr[cur++].h = b;
            arr[cur].x = min(b, c),  arr[cur].y = max(b, c),  arr[cur++].h = a;
        }
        sort(arr,  arr + cur, cmp);
        memset(dp, 0, sizeof(dp));

        for(int i = 0; i < cur; i++){
            int maxs = 0;
            for(int j = 0; j < i; j++){
                if(arr[j].x < arr[i].x && arr[j].y < arr[i].y){找出符合`x < d[i].x, y < d[i].y`的最大h和
                    maxs = max(maxs,    dp[j]);
                }
            }
            dp[i] = maxs +  arr[i].h;
         }

        int maxs = dp[0];
        for(int i = 0; i < cur; i++){
            if(dp[i] > maxs)
                    maxs = dp[i];
        }
        printf("Case %d: maximum height = %d\n",cas++, maxs);
    }
    return 0;
}