A group of researchers are designing an experiment to test the IQ of a monkey. They will hang a banana at the roof of a building, and at the mean time, provide the monkey with some blocks. If the monkey is clever enough, it shall be able to reach the banana by placing one block on the top another to build a tower and climb up to get its favorite food.

The researchers have 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 want to make sure that the tallest tower possible by stacking blocks can reach the roof. The problem is 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 because there has to be some space for the monkey to step on. 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 monkey 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

题目的大意就是给你n个立方体的长宽高，然后让你用这n种立方体来搭一个类似金字塔的东西，并且下一层的边要严格大于上一层的边（即不会出现等于的情况），让你求出最大的高度，每个立方体可以用无数次。

刚拿到这道题的时候一脸懵逼，在想到底怎么用dp来做，想了很久后发现其实一个立方体可以按照3个面划分为3个矩形，如图


当我们把一个立方体划分为3个矩形a,b,c后，再将每个矩形的长和宽交换一下，变为6个矩形，（因为搭金字塔时可以长对应长，也可以长对应宽）题目就是一个简单的求最长上升子序列LIS。

状态转移方程：

dp[i] = max(dp[i],dp[j]+b[i].z);

用dp[i]来记录当前的最大高度，dp[j]表示上一次操作的最大高度，如果dp[i]  >  dp[j]+b[i].z，则以第i个为起点，反之则将第i个加入原来的序列。（b[i].z是当前矩形对应的立方体的高度）。


上代码：

#include <iostream>
#include <string>
#include <sstream>
#include <stdio.h>
#include <stdlib.h>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <set>
#include <sstream>
#include <map>
#include <cctype>

using namespace std;
#define Start clock_t start = clock();
#define End clock_t end = clock();
#define Print cout<<(double)(end-start)/CLOCKS_PER_SEC*1000<<"ºÁÃë"<<endl;

const int maxn = 1000 + 5;

struct Blocks{
    int x,y,z;
}b[maxn];//立方体的长宽高
bool cmp(Blocks a,Blocks b){
    if(a.x == b.x) return a.y < b.y;
    else return a.x < b.x;
}
int dp[maxn];
int main()
{
    int n,num = 1;
    int x,y,z;
    while(cin>>n && n){
        int t = 0;
        for(int i = 0;i < n;i++){
            cin>>x>>y>>z;
            //将每个立方体划分为6个矩形
            b[t].x = x;b[t].y = y;b[t].z = z;t++;
            b[t].x = x;b[t].y = z;b[t].z = y;t++;
            b[t].x = y;b[t].y = x;b[t].z = z;t++;
            b[t].x = y;b[t].y = z;b[t].z = x;t++;
            b[t].x = z;b[t].y = x;b[t].z = y;t++;
            b[t].x = z;b[t].y = y;b[t].z = x;t++;
        }
        sort(b,b+t,cmp);
        dp[0] = b[0].z;
        int maxi = 0;
        for(int i = 1;i < t;i++){
            dp[i] = b[i].z;
            for(int j = 0;j < i;j++){
                if(b[j].x < b[i].x && b[j].y < b[i].y)
                    dp[i] = max(dp[i],dp[j]+b[i].z);
            }
            maxi = max(maxi,dp[i]);
        }
        cout<<"Case "<<num++<<": maximum height = "<<maxi<<endl;
    }
    return 0;
}

希望能对大家有帮助！

点赞