`
Simone_chou
  • 浏览: 182753 次
  • 性别: Icon_minigender_2
  • 来自: 广州
社区版块
存档分类
最新评论

Monkey and Banana(DP)

 
阅读更多

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.
 

 

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 (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

    Monkey-banana-catch

    JSU_动态规划_dp1

    最基础的DP题目解题报告,适合初学者!动态规划(DP1) ...解题报告: 1001 计算直线的交点数 1002 FatMouse's Speed1003 Common ... 1006 免费馅饼 1007 Humble Numbers1008 Monkey and Banana 1009 龟兔赛跑 1010 数塔

    Monkey测试结果分析

    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...

    学习Monkey使用说明

    1、 Monkey测试简介 Money是Android中的一个命令行工具,可以运行在模拟器里或实际设备中它向系统发送伪随机的用户事件流(如按键输入、触摸屏输入、手势输入等),实现对正在开发的应用程序进行压力测试。 Monkey测试...

    Line 6 Monkey

    Line 6 Monkey

    Monkey Banana-crx插件

    语言:English 覆盖新的标签页 一个可口的新标签页,上面有猴宝宝本人的励志名言!

    monkey指定页面测试

    monkey指定页面测试https://blog.csdn.net/u014248060/article/details/80538208

    python-spidermonkey

    《用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测试快捷配置脚本

    monkey测试脚本使用说明 步骤一: MMI开机,确认USB调试模式已打开,USB线连接电脑端,确认adb已连接 步骤二: 打开monkeyConfig.ini 配置文件,配置需要执行monkey测试的应用包名及根据文档中备注提示配置其他...

    Monkey源码

    monkey

    获取monkey pid的源码

    这个源码能够获取到正在执行的monkey的pid,可以用这个pid结束monkey的执行

    tampermonkey.zip

    Tampermonkey 是一款免费的浏览器扩展和最为流行的用户脚本管理器,它适用于 Chrome, Microsoft Edge, Safari, Opera Next, 和 Firefox。 虽然有些受支持的浏览器拥有原生的用户脚本支持,但 Tampermonkey 将在您的...

    noip2007模拟题

    noip模拟题带测试数据NOIP2007 复赛模拟练习(一) 1、01序列 2、 农场 3、 白色矩形 4、 Subset 5、 步步为零游戏 6、 Monkey and Banana

    Android_Monkey自动测试工具使用报告

    什么是Monkey? 使用Monkey做自动化。 Monkey工具的命令

    利用 Monkey 命令操作屏幕快速滑动

    一、Monkey测试简介 Monkey测试是Android平台自动化测试的一种手段,通过Monkey程序模拟用户触摸屏幕、滑动Trackball、按键等操作来对设备上的程序进行压力测试,检测程序多久的时间会发生异常。 二、Monkey程序介绍...

    tampermonkey-4.18.1.xpi

    tampermonkey-4.18.1.xpi

    monkey命令

    monkey命令monkey命令monkey命令monkey命令monkey命令monkey命令

    Tampermonkey.zip

    Tampermonkey 是一款免费的浏览器扩展和最为流行的用户脚本管理器,它适用于 Chrome, Microsoft Edge, Safari, Opera Next, 和 Firefox。 虽然有些受支持的浏览器拥有原生的用户脚本支持,但 Tampermonkey 将在您的...

    tampermonkey.7z

    Tampermonkey 是一款免费的浏览器扩展和最为流行的用户脚本管理器,它适用于 Chrome, Microsoft Edge, Safari, Opera Next, 和 Firefox。 虽然有些受支持的浏览器拥有原生的用户脚本支持,但 Tampermonkey 将在您的...

    Tampermonkey油猴插件 v4.16

    Tampermonkey 油猴插件是一款免费的浏览器扩展和最为流行的用户脚本管理器,它适用于 Chrome, Microsoft Edge, Safari, Opera Next, 和 Firefox。虽然有些受支持的浏览器拥有原生的用户脚本支持,但 Tampermonkey...

Global site tag (gtag.js) - Google Analytics