HDU 1069 Monkey and Banana(dp)

제목 링크: HDU 1069 Monkey and Banana
dp.
나는 이 문제의 난점은 네모난 블록의 무한한 문제를 해결하는 데 있다고 생각한다. 코드로 전환하면 한 네모난 블록이 여섯 개의 네모난 블록으로 변하는 것이다.그리고 순서를 정하면 나머지는 간단해진다.
blocks[i].height는 i번째 블록이 맨 밑에 있을 때의 최대 높이를 나타낸다.
코드를 구체적으로 보세요.

#include <iostream>
#include <algorithm>
#include <stdio.h>

using namespace std;

const int MAX_N = 1000;
struct Block
{
    int x,y,z;
    int height;
};
Block blocks[MAX_N];
int n,x,y,z,k,_max;
int cmp(Block a, Block b)
{
    if(a.x < b.x)
        return 1;
    if(a.x == b.x && a.y < b.y)
        return 1;
    return 0;
}
void f(int x, int y, int z)
{
    blocks[k].x = x;
    blocks[k].y = y;
    blocks[k].height = blocks[k].z = z;
    k++;
    blocks[k].x = x;
    blocks[k].y = z;
    blocks[k].height = blocks[k].z = y;
    k++;
    blocks[k].x = y;
    blocks[k].y = x;
    blocks[k].height = blocks[k].z = z;
    k++;
    blocks[k].x = y;
    blocks[k].y = z;
    blocks[k].height = blocks[k].z = x;
    k++;
    blocks[k].x = z;
    blocks[k].y = x;
    blocks[k].height = blocks[k].z = y;
    k++;
    blocks[k].x = z;
    blocks[k].y = y;
    blocks[k].height = blocks[k].z = x;
    k++;
}
int main()
{
    int cnt = 0;
    while(cin >> n, n)
    {
        _max = 0;
        k = 0;
        for(int i = 0;i < n;i++)
        {
            cin >> x >> y >> z;
            f(x, y, z);
        }
        sort(blocks, blocks + k, cmp);
        for(int i = 0;i < k;i++)
        {
            for(int j = 0 ;j < i;j++)
            {
                if(blocks[i].x > blocks[j].x && blocks[i].y > blocks[j].y)
                    blocks[i].height = max(blocks[i].height, blocks[j].height + blocks[i].z);
            }
            _max = max(_max, blocks[i].height);
        }
        //cout << _max << endl;
        printf("Case %d: maximum height = %d
",++cnt,_max);
    }
    return 0;
}