Monkey and Banana
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 7416 Accepted Submission(s): 3813
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.
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.
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 <= 30),代表给出 n 种长方体,给出每个长方体的三个长度,可以任意摆放任意使用多个,问叠放起来的最高高度是多少,输出最高的高度。底部的两边必须严格小于下面的底部才能往上叠放。
思路:
DP。类似于矩形嵌套的变形。找最长上升子序列。将一个长方体拆开六种来判断即可,dp[ i ] 表示到第 i 个长方体的最高高度是多少。
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef struct { int l, w, h; } node; node num[200]; int ans, dp[200]; bool cmp (node a, node b) { if (a.l != b.l) return a.l > b.l; if (a.w != b.w) return a.w > b.w; return a.h > b.h; } int main() { int n, t = 0; while (~scanf("%d", &n) && n) { ans = 0; memset(dp, 0, sizeof(dp)); while (n--) { int a, b, c; scanf("%d%d%d", &a, &b, &c); num[ans].l = a, num[ans].w = b, num[ans++].h = c; num[ans].l = a, num[ans].w = c, num[ans++].h = b; num[ans].l = b, num[ans].w = a, num[ans++].h = c; num[ans].l = b, num[ans].w = c, num[ans++].h = a; num[ans].l = c, num[ans].w = a, num[ans++].h = b; num[ans].l = c, num[ans].w = b, num[ans++].h = a; } sort(num, num + ans, cmp); int max_high = 0; dp[0] = num[0].h; for (int i = 1; i < ans; ++i) { int max_temp = 0; for (int j = 0; j < i; ++j) { if (num[j].l > num[i].l && num[j].w > num[i].w) max_temp = max(max_temp, dp[j]); } dp[i] = max_temp + num[i].h; max_high = max(max_high, dp[i]); } printf("Case %d: maximum height = %d\n", ++t, max_high); } return 0; }
相关推荐
Monkey-banana-catch
最基础的DP题目解题报告,适合初学者!动态规划(DP1) ...解题报告: 1001 计算直线的交点数 1002 FatMouse's Speed1003 Common ... 1006 免费馅饼 1007 Humble Numbers1008 Monkey and Banana 1009 龟兔赛跑 1010 数塔
l monkey --pkg-whitelist-file /data/local/tmp/whitelist.txt --throttle 500 -s 100 --ignore-crashes --ignore-timeouts --ignore-security-exceptions --ignore-native-crashes --monitor-native-crashes -v -v...
1、 Monkey测试简介 Money是Android中的一个命令行工具,可以运行在模拟器里或实际设备中它向系统发送伪随机的用户事件流(如按键输入、触摸屏输入、手势输入等),实现对正在开发的应用程序进行压力测试。 Monkey测试...
Line 6 Monkey
语言:English 覆盖新的标签页 一个可口的新标签页,上面有猴宝宝本人的励志名言!
monkey指定页面测试https://blog.csdn.net/u014248060/article/details/80538208
《用perl解析JavaScript之JavaScript模块的安装--SpiderMonkey》 安装依赖软件: 安装pyrex:sudo apt-get install python-pyrex 安装g++:sudo apt-get install g++ 安装libjs.so: $ tar zxvf js-1.7.0.tar...
monkey测试脚本使用说明 步骤一: MMI开机,确认USB调试模式已打开,USB线连接电脑端,确认adb已连接 步骤二: 打开monkeyConfig.ini 配置文件,配置需要执行monkey测试的应用包名及根据文档中备注提示配置其他...
monkey
这个源码能够获取到正在执行的monkey的pid,可以用这个pid结束monkey的执行
Tampermonkey 是一款免费的浏览器扩展和最为流行的用户脚本管理器,它适用于 Chrome, Microsoft Edge, Safari, Opera Next, 和 Firefox。 虽然有些受支持的浏览器拥有原生的用户脚本支持,但 Tampermonkey 将在您的...
noip模拟题带测试数据NOIP2007 复赛模拟练习(一) 1、01序列 2、 农场 3、 白色矩形 4、 Subset 5、 步步为零游戏 6、 Monkey and Banana
什么是Monkey? 使用Monkey做自动化。 Monkey工具的命令
一、Monkey测试简介 Monkey测试是Android平台自动化测试的一种手段,通过Monkey程序模拟用户触摸屏幕、滑动Trackball、按键等操作来对设备上的程序进行压力测试,检测程序多久的时间会发生异常。 二、Monkey程序介绍...
tampermonkey-4.18.1.xpi
monkey命令monkey命令monkey命令monkey命令monkey命令monkey命令
Tampermonkey 是一款免费的浏览器扩展和最为流行的用户脚本管理器,它适用于 Chrome, Microsoft Edge, Safari, Opera Next, 和 Firefox。 虽然有些受支持的浏览器拥有原生的用户脚本支持,但 Tampermonkey 将在您的...
Tampermonkey 是一款免费的浏览器扩展和最为流行的用户脚本管理器,它适用于 Chrome, Microsoft Edge, Safari, Opera Next, 和 Firefox。 虽然有些受支持的浏览器拥有原生的用户脚本支持,但 Tampermonkey 将在您的...
Tampermonkey 油猴插件是一款免费的浏览器扩展和最为流行的用户脚本管理器,它适用于 Chrome, Microsoft Edge, Safari, Opera Next, 和 Firefox。虽然有些受支持的浏览器拥有原生的用户脚本支持,但 Tampermonkey...