HDU1069_Monkey and Banana【LCS】

HDU1069_Monkey and Banana【LCS】

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

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;
}

版权声明:本文博客原创文章,博客,未经同意,不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117275.html原文链接:https://javaforall.cn

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

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

(0)


相关推荐

  • 优秀的数据工程师,怎么用 Spark 在 TiDB 上做 OLAP 分析[通俗易懂]

    优秀的数据工程师,怎么用 Spark 在 TiDB 上做 OLAP 分析[通俗易懂]优秀的数据工程师,怎么用 Spark 在 TiDB 上做 OLAP 分析

  • 美女登场「建议收藏」

    美女登场「建议收藏」不怕大家笑话,我大学毕业时,还是个处长,所谓处长就是没有经过女人滋润的那种,我想大家都知道我是什么意思的。其实,上大学的时候我还是有些女人缘的,毕竟在班上我的学习成绩还是走在了同学们的前列,这是一笔不小的资本。你不知道,只要到了考试前一个月左右,我是很跑火的,我们班上那些天天浸泡在女孩子堆的家伙就要开始巴结我,请我吃饭,因为他们要拿到毕业证,还是需要过我这关的,考试的时候他们好抄袭我的,我要是给他

  • 独立成分分析 ( ICA ) 与主成分分析 ( PCA ) 的区别「建议收藏」

    独立成分分析 ( ICA ) 与主成分分析 ( PCA ) 的区别「建议收藏」1.前言参考资料:https://www.zhihu.com/question/28845451书上写的是:1.主成分分析假设源信号间彼此非相关,独立成分分析假设源信号间彼此独立。2.主成分分析认为主元之间彼此正交,样本呈高斯分布;独立成分分析则不要求样本呈高斯分布。在利用最大化信息熵的方法进行独立成分分析的时候,需要为源信号假定一个概率密度分布函数g’,进而找出使得g(Y)=g…

  • Linux查看redis版本(查看mongodb版本)

    快半年没有在Linux中使用redis了,命令有些生疏了,网上很多博文也不对,不知道博主是否直接复制的来的。以下为重新整理资料,便于忘记时候复习首先进入cd/usr/local目录不用说了我把redis安装到了redis文件夹中了,在bin目录下找到redis-server使用./redis-server–version查看版本信息[red@RedFaceloc…

  • EXE文件结构及读取方法

    EXE文件结构及读取方法

  • 指令周期的四个阶段_单片机指令周期与机器周期

    指令周期的四个阶段_单片机指令周期与机器周期时钟周期时钟周期也称为振荡周期,定义为时钟脉冲的倒数(可以这样来理解,时钟周期就是单片机外接晶振的倒数,例如12M的晶振,它的时间周期就是1/12us),是计算机中最基本的、最小的时间单位。在一个时钟周期内,CPU仅完成一个最基本的动作。对于某种单片机,若采用了1MHZ的时钟频率,则时钟周期为1us;若采用4MHZ的时钟频率,则时钟周期为250ns。由于时钟脉冲是计算机的基本工作脉冲…

    2022年10月13日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号