首页 > 代码库 > HDU1069_Monkey and Banana【LCS】
HDU1069_Monkey and Banana【LCS】
Monkey and Banana
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 7823 Accepted Submission(s): 4033
Problem Description
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块长宽高分别为x*y*z的砖。猴子想要
垒一座砖塔去吃香蕉。垒塔的时候上边的砖必须严格的比下边的砖小(上边砖
长<下边砖长 && 上边砖宽<下边砖宽)。砖有无数块，问最高能垒多高。
思路：虽然砖有无数块。但是长为x宽为y规模的砖只能用一块。因为上下砖
长和宽都不等。但是一块砖有好多种放法。这里先对x，y，z递增排序。建
一个结构体存摆放方法。让x为宽，y为长，z为高为一种摆法，让x为宽，z为
长，y为高为一种摆法，y为宽，z为长，x为高为第三种摆法。
这里为什么不将长宽调换位置来作为一种摆法？
其实是没必要这样。加上也对，不加也不会错。
因为上下砖的长宽是严格不等的。若让x为长，y为宽，z为高。
假设x，y，z的长度都不一样。则根据上边三种摆法。
最下边的砖为宽为y，长为z，高为x的砖。
在往上的砖为宽为x，长为y，高为z的砖。
另一块砖不能摆放。
加上y为宽，x为长，z为高的砖后。不能摆放。
同理，其他两种摆放方法也不成立。
把所有砖的摆放方法存起来之后，对砖的底面面积(长*宽)进行升序排列。
之后就是类似求最长递增子序列的最大和了。
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct block
{
int x;
int y;
int z;
int area;
}Block[330];
int dp[330];
int cmp(block a,block b)
{
return a.area < b.area;
}
int main()
{
int N,a[3],kase = 1;
while(~scanf("%d",&N) && N)
{
int num = 0;
memset(dp,0,sizeof(dp));
memset(Block,0,sizeof(Block));
for(int i = 0; i < N; i++)
{
scanf("%d%d%d",&a[0],&a[1],&a[2]);
sort(a,a+3);
Block[num].x = a[0],Block[num].y = a[1],Block[num].z = a[2],Block[num].area = Block[num].x*Block[num].y,num++;
Block[num].x = a[1],Block[num].y = a[2],Block[num].z = a[0],Block[num].area = Block[num].x*Block[num].y,num++;
Block[num].x = a[0],Block[num].y = a[2],Block[num].z = a[1],Block[num].area = Block[num].x*Block[num].y,num++;
}
sort(Block,Block+num,cmp);
int Max = 0;
for(int i = 0; i < num; i++)
{
dp[i] = Block[i].z;
for(int j = 0; j < i; j++)
{
if(Block[j].x < Block[i].x && Block[j].y < Block[i].y)
dp[i] = max(dp[i],dp[j]+Block[i].z);
}
Max = max(dp[i],Max);
}
printf("Case %d: maximum height = %d\n",kase++,Max);
}
return 0;
}
HDU1069_Monkey and Banana【LCS】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。