The Tower of Babylon UVA - 437(바빌론 타워, DP)

Perhaps you have heard of the legend of the Tower of Babylon. Nowadays many details of this tale have been forgotten. So now, in line with the educational nature of this contest, we will tell you the whole story: The babylonians had n types of blocks, and an unlimited supply of blocks of each type. Each type-i block was a rectangular solid with linear dimensions (xi , yi , zi). A block could be reoriented so that any two of its three dimensions determined the dimensions of the base and the other dimension was the height. They wanted to construct the tallest tower possible by stacking blocks. The problem was that, in building a tower, one block could only be placed on top of another block as long as the two base dimensions of the upper block were both strictly smaller than the corresponding base dimensions of the lower block. This meant, for example, that blocks oriented to have equal-sized bases couldn’t be stacked. Your job is to write a program that determines the height of the tallest tower the babylonians can build with a given set of blocks. Input The input file will contain one or more test cases. The first line of each test case contains an integer n, representing the number of different blocks in the following data set. The maximum value for n is 30. Each of the next n lines contains three integers representing the values xi , yi and zi . Input is terminated by a value of zero (0) for n. Output For each test case, print one line containing the case number (they are numbered sequentially starting from 1) and the height of the tallest possible tower in the format ‘Case case: maximum height = height’ Sample Input 1 10 20 30 2 6 8 10 5 5 5 7 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 5 31 41 59 26 53 58 97 93 23 84 62 64 33 83 27 0 Sample Output Case 1: maximum height = 40 Case 2: maximum height = 21 Case 3: maximum height = 28 Case 4: maximum height = 342
제목: 나무 덩어리를 쌓는 데 있어서 윗부분의 밑면의 길이는 반드시 다음 덩어리의 길이보다 작아야 하며, 최대 쌓는 높이가 얼마나 되는지 물어야 한다.사고방식: 고전적인 문제입니다. 지금 쓰세요.호남 여러 학교에서 비슷한 것을 만났지만 2차원 모델이다. 그 문제는 그림을 만드는 방법을 사용했고 H-Highest Tower CSU-2017도 dp의 방법으로 만들 수 있을 것이다. 다음에 다시 보충할 것이다.

상태 정의: dp[i][j]는 i번째 나무 블록을 선택하고 j조의 가장자리를 높게 선택한다(가장자리 길이가 많을 수 있기 때문에 가장자리 길이로 상태가 열리지 않을 수 있음을 표시한다)

자상태: 모든 길이와 너비가 이 나무토막보다 작은 상태

상태이동: 취자상태max

세부 사항 구현: 기억화 검색을 사용하여 상태 이동을 나타낸다.ans를 사용하여 dp수 그룹을 표시하고 코드의 양을 간소화합니다.ans가 하위 상태의 max를 선택한 것을 기억하려면 현재 높이를 추가해야 합니다.

왜: 관건은 상태 표시 부분에 있는데 이 부분은 어떻게 생각해낸 거예요?한 가지 주의해야 할 것은 우리가 나무를 쌓을 때 밑면만 고려하고 밑면이 더 작으면 쌓을 수 있으며 높이는 결정의 결과이기 때문에 우리는 밑면만 상태로 하고 가장 좋은 결과를 얻는 것이 가장 높은 높이이다.

#include
#include
#include
#include
#include

using namespace std;
const int maxn = 105;

int n;
int dp[maxn][3];//  i     j              
int cube[maxn][3];

void trans(int *v,int a,int b)
{
    int cnt = 0;
    for(int i = 1;i <= 3;i++)
    {
        if(i == b)continue;
        v[cnt++] = cube[a][i];
    }
}
int solve(int a,int b)
{
    int &ans = dp[a][b];// ans   dp  ，    
    if(ans > 0)
        return ans;
    ans = 0;
    
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= 3;j++)
        {
            int v1[2],v2[2];
            trans(v1,i,j);
            trans(v2,a,b);
            if(v1[0] < v2[0] && v1[1] < v2[1])
                ans = max(ans,solve(i,j));
        }
    }
    ans += cube[a][b];
    return ans;
}

int main()
{
    
    int kase = 0;
    while(~scanf("%d",&n) && n)
    {
        memset(dp,0,sizeof(dp));
        for(int i = 1;i <= n;i++)
        {
            for(int j = 1;j <= 3;j ++)
            {
                scanf("%d",&cube[i][j]);
            }
            sort(cube[i] + 1,cube[i] + 1 + 3);
        }
        
        int ans = 0;
        for(int i = 1;i <= n;i++)
        {
            for(int j = 1;j <= 3;j++)
            {
                ans = max(ans,solve(i,j));
            }
        }
        printf("Case %d: maximum height = ",++kase);
        printf("%d
",ans);
    }
    return 0;
}