oyjpArt ACM/ICPC算法程序設(shè)計(jì)空間

很羨慕你的說(shuō)，大學(xué)里能夠這么有耐心的研究算法。我一直在考慮我能夠在計(jì)算機(jī)領(lǐng)域內(nèi)發(fā)展到什么層次？恐怕這些我不感興趣的算法以后會(huì)成為我很大的阻礙阿 ！

是自從接觸ACM以來(lái)才知道自己原來(lái)水平有多菜~~（呵呵） 后來(lái)才知道原來(lái)自己與別人的差距有多大啊~~ 從最簡(jiǎn)單的算法開(kāi)始認(rèn)認(rèn)真真學(xué) 爭(zhēng)取早日走出菜鳥(niǎo)的圈圈

感覺(jué)就是個(gè)插入排序問(wèn)題,其插入排序?qū)崿F(xiàn)見(jiàn)http://www.shnenglu.com/SoRoMan/archive/2006/08/09/11053.html

非常感謝SoRoMan對(duì)這道題的關(guān)注，甚至還為此寫出了完整的程序。
程序?qū)懙暮芷粒浅８兄x。
由于本人的疏忽 題目描述地不是很清楚，所以特此也把整個(gè)原題貼出來(lái)（由于已經(jīng)寫了簡(jiǎn)述，故不再翻譯原題（呵呵，實(shí)際上是沒(méi)那英文水準(zhǔn)~~-_-))

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

我也跑去做做：）

非常感謝師兄的提示，我DP一貫很差，今個(gè)有過(guò)了一個(gè)。。。受益匪淺！TH

師兄？你是？

lz的沒(méi)看太明白呢，不過(guò)我用深度優(yōu)先搜索的方法做出來(lái)了哦
算法分析如下：
1） 將n個(gè)石塊存入blocks[3n]中（如lz一樣把每一塊分成三塊，但不用求面積，也不用排序）
2） 構(gòu)建blocks的有向鄰接表adj。（eg blocks[i]--> block[j] 的條件是 i的底部長(zhǎng)寬都比j的小 即，嚴(yán)格小于）
3） 深度優(yōu)先搜索整個(gè)鄰接表。并用一個(gè)數(shù)組height[n]記錄以每一個(gè)節(jié)點(diǎn)為最底層塊的時(shí)候的最大高度
4） 遍歷height[n],值最大的那個(gè)就是所求的最大高度了。