# 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

```#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

struct block
{
int x;
int y;
int z;
int area;
}Block;
int dp;
int cmp(block a,block b)
{
return a.area < b.area;
}
int main()
{
int N,a,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,&a,&a);
sort(a,a+3);
Block[num].x = a,Block[num].y = a,Block[num].z = a,Block[num].area = Block[num].x*Block[num].y,num++;
Block[num].x = a,Block[num].y = a,Block[num].z = a,Block[num].area = Block[num].x*Block[num].y,num++;
Block[num].x = a,Block[num].y = a,Block[num].z = a,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;
}
```

【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛

【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0) ### 相关推荐

• #### 关机程序（C语言）

关机程序（C语言）分享一个小小的关机程序，可你发送给你的好友哦！！！#include<stdio.h>#include<string.h>//strcmp()#include<st

• #### Java学习之继承与抽象篇

Java学习之继承与抽象篇0x00前言前面讲到了面向对象，面向对象的三大特性是封装、继承、多态。那么这次就来讲讲继承。0x01继承概述：多个类中存在相同属性和行为时，将这些内容抽取到单独一

• #### 木马入门

木马入门木马是如何编写的(一)特洛依木马这个名词大家应该不陌生，自从98年“死牛崇拜”黑客小组公布BackOrifice以来，木马犹如平地上的惊雷，使在Dos——Windows时代中长大的中国网民从五彩缤纷的网络之梦中惊醒，终于认识到的网络也有它邪恶的一面，一时间人心惶惶。　　我那时在《电脑报》上看到一篇文章，大意是一个菜鸟被人用BO控制了，吓得整天吃不下饭、睡不着觉、上不了网，到处求救！

• #### linux 驱动移植_免驱动led灯好吗

linux 驱动移植_免驱动led灯好吗通过前两篇文章的介绍，我们已经把linux内核移植到了tiny210上，但是看到的现象都是通过超级终端来观察的，下面了，我们介绍一下led灯的移植，给大家一个更直观的感受。这篇文章主要的内容如下：1.对平台总线的简介；2.led驱动的移植。一.平台总线   首先介绍一下，我们为什么要简单介绍一下平台总线呢？因为我们是做led驱动的移植，而不是自己编写led的驱动代码。我们要移植

• #### 数据库的or语句_oracle数据库常用sql语句

数据库的or语句_oracle数据库常用sql语句一、ORACLE的启动和关闭1、在单机环境下要想启动或关闭ORACLE系统必须首先切换到ORACLE用户，如下su-oraclea、启动ORACLE系统oracle>svrmgrlSVRMGR>connectinternalSVRMGR>startupSVRMGR>quitb、关闭ORACLE系统oracle>svrmgrlSVRMGR&g…

• #### POJ 3580 SuperMemo

POJ 3580 SuperMemo 