UVA 437 The Tower of Babylon

有些类似“叠箱子”问题，看起来一种砖有无限多个，其实最多只能用到两次。

说下我的思路吧，一块砖有3个数据，虽然3！＝6，但本质上还是只有3种，把这三种都表示出来，使x<=y；这样就有了3n组数据。因为我不会建图，就把这3n组数据再排列一下，使一块砖只能放到它后面的砖之上，而绝不能放到之前的砖上，即按x为一级y为二级升序排列，结合之前的x<=y，就能达到目的了。比如：两块砖，31*41*59和26*53*58，经过排序后变为：

26 53 58

26 58 53

31 41 59

31 59 41

41 59 31

53 58 26

接下来就是DP了……

这题我做得很坎坷，因为想用sort不用qsort，又写了回好久没写的C++；但是坑爹的sort不支持二维数组，只好改为结构体；最后因为更新状态的细节又WA了好几次。我把WA的代码贴一下：

t = 0;

for

{

　　for

}

这是其一；

for

{

　　t = 0;

　　for

}

这是其二。至于为什么错了，我就不说了，读者自己想吧。

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
typedef struct
{
    int arr[3];
}Box;
Box a[100];
bool cmp(Box a,Box b)
{
    if(a.arr[0] != b.arr[0])
        return a.arr[0] < b.arr[0];
    else if(a.arr[1] != b.arr[1])
        return a.arr[1] < b.arr[1];
    else return a.arr[2] < b.arr[2];
}
int ok(Box a,Box b)
{
    return (a.arr[0] < b.arr[0] && a.arr[1] < b.arr[1]);
}
int main()
{
    int n,m=0,i,j,t,max;
    while(cin>>n,n)
    {
        m++;
        for(i = 0; i < 3*n; i += 3)
        {
            cin>>a[i].arr[0]>>a[i].arr[1]>>a[i].arr[2];
            sort(a[i].arr,a[i].arr+3);
            a[i+1].arr[0] = a[i].arr[0];
            a[i+1].arr[1] = a[i].arr[2];
            a[i+1].arr[2] = a[i].arr[1];
            a[i+2].arr[0] = a[i].arr[1];
            a[i+2].arr[1] = a[i].arr[2];
            a[i+2].arr[2] = a[i].arr[0];
         }
        sort(a,a+3*n,cmp);
        max = 0;
        for(i = 3*n-2; i >= 0; i--)
        {
            t = a[i].arr[2];
            for(j = i+1; j < 3*n; j++)
            {
                if(ok(a[i],a[j]) && a[i].arr[2]+a[j].arr[2] > t)
                    t = a[i].arr[2]+a[j].arr[2];
            }
            a[i].arr[2] = t;
            if(t > max) max = t;
        }
        printf("Case %d: maximum height = %d\n",m,max);
    }
    return 0;
}