oyjpArt ACM/ICPC算法程序设计空间

// I am new in programming, welcome to my blog
I am oyjpart(alpc12, 四城)
posts - 224, comments - 694, trackbacks - 0, articles - 6
前面做的那道Bridging Signals是有技巧性的题目 因为题目要求o(n*logn)的复杂度
刚才又做了一道The Tower of Babylon 题目不难 但是堪称经典啦

简述: 有N种石头(每种数量无限)题目给出每种的长宽高 先要求将其按底面积递减的顺序从下往上堆(注意是严格递减 对应边相等不算) 问最多可以堆多高?

分析:首先我想的是处理底面积的时候可能要分情况讨论,但是比较复杂。于是干脆将每块石头变成3块(这样就可以得到石头的真正总数了)。block代表所有石头 有3个成员x,y,z.

 然后将其按照底面积大小从大到小排序。建立一个数组h[],h[i]记录的是当前石头作为顶上石头时候的总高度。于是状态转移方程为 h[i] = max {h[j]+block[i].z)。输出最大的height[i]就可以了

呵呵 做完之后不知怎么觉得好爽啊~~

Feedback

# re: 今天我做的一道经典动归题The Tower of Babylon   回复  更多评论   

2006-08-09 08:57 by cmdn
很羡慕你的说,大学里能够这么有耐心的研究算法。我一直在考虑我能够在计算机领域内发展到什么层次?恐怕这些我不感兴趣的算法以后会成为我很大的阻碍阿 !

# re: 今天我做的一道经典动归题The Tower of Babylon   回复  更多评论   

2006-08-09 11:03 by sicheng
是自从接触ACM以来才知道自己原来水平有多菜~~(呵呵) 后来才知道原来自己与别人的差距有多大啊~~ 从最简单的算法开始认认真真学 争取早日走出菜鸟的圈圈

# re: 今天我做的一道经典动归题The Tower of Babylon   回复  更多评论   

2006-08-09 18:14 by SoRoMan
感觉就是个插入排序问题,其插入排序实现见http://www.cppblog.com/SoRoMan/archive/2006/08/09/11053.html

# re: 今天我做的一道经典动归题The Tower of Babylon   回复  更多评论   

2006-08-09 19:11 by sicheng
非常感谢SoRoMan对这道题的关注,甚至还为此写出了完整的程序。
程序写的很漂亮,非常感谢。
由于本人的疏忽 题目描述地不是很清楚,所以特此也把整个原题贴出来(由于已经写了简述,故不再翻译原题(呵呵,实际上是没那英文水准~~-_-))

The Tower of Babylon
Time Limit:1000MS Memory Limit:65536K
Total Submit:230 Accepted:147

Description
Perhaps you have heard of the legend of the Tower of Babylon. Nowadays many details of this tale have been forgotten. So now, in line with the educational nature of this contest, we will tell you the whole story:
The babylonians had 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 wanted to construct the tallest tower possible by stacking blocks. The problem was 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. 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 babylonians can build with a given set of blocks.

Input
The input 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


Source
Ulm Local 1996

# re: 今天我做的一道经典动归题The Tower of Babylon   回复  更多评论   

2006-08-10 02:45 by
我也跑去做做:)

# re: 今天我做的一道经典动归题The Tower of Babylon   回复  更多评论   

2007-07-29 21:23 by keky
非常感谢师兄的提示,我DP一贯很差,今个有过了一个。。。受益匪浅!TH

# re: 今天我做的一道经典动归题The Tower of Babylon [未登录]  回复  更多评论   

2007-07-30 15:35 by oyjpArt
师兄?你是?

# re: 今天我做的一道经典动归题The Tower of Babylon   回复  更多评论   

2009-04-30 14:32 by 尖尖角
lz的没看太明白呢,不过我用深度优先搜索的方法做出来了哦
算法分析如下:
1) 将n个石块存入blocks[3n]中(如lz一样把每一块分成三块,但不用求面积,也不用排序)
2) 构建blocks的有向邻接表adj。(eg blocks[i]--> block[j] 的条件是 i的底部长宽都比j的小 即,严格小于)
3) 深度优先搜索整个邻接表。并用一个数组height[n]记录以每一个节点为最底层块的时候的最大高度
4) 遍历height[n],值最大的那个就是所求的最大高度了。

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理