题目：
Monkey and Banana |
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) |
Total Submission(s): 720 Accepted Submission(s): 455 |
|
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.
|
Input The input file will contain one or more test cases. The first line of each test case contains an integer 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 110 20 3026 8 105 5 571 1 12 2 23 3 34 4 45 5 56 6 67 7 7531 41 5926 53 5897 93 2384 62 6433 83 270
|
Sample Output Case 1: maximum height = 40Case 2: maximum height = 21Case 3: maximum height = 28Case 4: maximum height = 342
|
|
Source University of Ulm Local Contest 1996
|
Recommend JGShining |
题目大意：
把一堆长方体叠在一起。叠加的条件是：下面的长方体的长和宽都要比上面的长方体的长和宽都要长。在满足条件的情况下，求这样叠起来的长方体的最大高度。
题目分析：
都是属于在第一关键字有序的情况下根据第二关键字求最长上升子序列的高度的题目。其实细细看一下，这道题和
Super Jumping! Jumping! Jumping!也有共通之处，那就是都是求一个LIS的距离之和(高度之和的问题)。
1)要求第一关键字有序，那么我们就现根据第一关键字排一下序，即可。
2)这道题还需要注意的是，在这里同一组数据允许形成不同的长方体。也就是长、宽、高的数值可以互换。但是这样也仅仅只能是形成最多3种不同的三角形。为什么呢？因为早高一样的情况下，长宽不同的长方体换一个角度看其实是同一个长方体。所以根据排列组合的思想，这里形成的长方体的个数应该是A(3,1)而不是A(3，3);
代码如下：
/*
* e.cpp
*
* Created on: 2015年2月11日
* Author: Administrator
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 100;
struct Block{
int length;//砖块的长度
int width;//砖块的宽度
int height;//砖块的高度
int sum;//到目前这个砖块所能达到的最大的高度
}block[maxn];
int cnt = 1;//用来标记砖块的数量
int n;
bool cmp(const Block& a,const Block& b){
if(a.length != b.length){//当长度不一样的时候
return a.length > b.length;//按长度降序排列
}
return a.width > b.width;//在长度一样的情况下,根据宽度降序排列
}
int LIS_Sum(){
int i;
int j;
int maxSum = -999;//最后反蝴蝶全局的最长上升子序列的高度
for(i = 1 ; i <= cnt ; ++i){///第一层循环:遍历每一个数
int temp = 0;//用于求到当前这个索引的最长上升子序列的最大高度
for(j = 1 ; j < i ; ++j){//第二层循环:遍历到当前这个数的前一个数
if(block[j].length > block[i].length && block[j].width > block[i].width){//如果能够构成题目所要求的序列(最长上升子序列)
if(temp < block[j].sum){//如果到索引j所达到的最长上升子序列的高度>目前所保存的最长上升子序列的高度
temp = block[j].sum;//更新目前最大的最长上升子序列的高度
}
}
}
block[i].sum = block[i].height + temp;//更新到索引i所能达到的最长上升子序列的高度
if(maxSum < block[i].sum){//如果到索引i所能达到的最长上升子序列的高度之和>全局的最长上升子序列的高度之和
maxSum = block[i].sum;//更新全局的最长上升子序列的高度之和
}
}
return maxSum;
}
int main(){
int counter = 1;
int d[3];
while(scanf("%d",&n)!=EOF,n){
memset(block,0,sizeof(block));
int i;
for(i = 1 ; i <= n ; ++i){
scanf("%d %d %d",&d[0],&d[1],&d[2]);
sort(d,d+3);//对输入序列排序
block[cnt].length = d[1];//注意,在这里要严格遵循长度>宽度的准则.否则这道题做不出来
block[cnt].width = d[0];
block[cnt].height = d[2];
cnt++;
block[cnt].length = d[2];
block[cnt].width = d[1];
block[cnt].height = d[0];
cnt++;
block[cnt].length = d[2];
block[cnt].width = d[0];
block[cnt].height = d[1];
cnt++;
}
cnt -= 1;
sort(block+1,block+1+cnt , cmp);//先按长度将徐排列
printf("Case %d: maximum height = %d\n",counter++,LIS_Sum());
}
return 0;
}