青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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://m.shnenglu.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],值最大的那個就是所求的最大高度了。
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            最新日韩在线| 激情综合久久| 亚洲视频精品在线| 一本色道久久88亚洲综合88| 欧美日精品一区视频| 欧美在线免费视频| 久久五月激情| 亚洲深夜福利| 午夜精品在线| 亚洲日本免费| 一区二区三区四区国产| 国产综合久久| 亚洲经典三级| 欧美三级网址| 免费永久网站黄欧美| 欧美日韩国产在线播放网站| 香蕉成人久久| 欧美成人精品三级在线观看 | 久久综合狠狠| 9人人澡人人爽人人精品| 性色av香蕉一区二区| 亚洲激情在线播放| 亚洲小视频在线观看| 国产在线日韩| 亚洲毛片一区| 亚洲成人在线免费| 亚洲素人一区二区| 亚洲人成小说网站色在线| 亚洲女爱视频在线| 在线亚洲免费视频| 久久视频一区二区| 先锋影音久久久| 欧美金8天国| 久热精品视频| 国产日韩欧美制服另类| 日韩一区二区高清| 亚洲精品日韩在线观看| 欧美中文在线视频| 欧美在线国产精品| 欧美日韩精品久久久| 欧美黄色aaaa| 狠狠狠色丁香婷婷综合激情| 一区二区不卡在线视频 午夜欧美不卡'| 国产一区欧美日韩| 亚洲一二三四区| 一本色道久久综合亚洲二区三区| 久久久久久自在自线| 欧美中文字幕视频在线观看| 欧美日韩一区三区| 亚洲国产精品久久久久秋霞蜜臀| 亚洲春色另类小说| 久久欧美肥婆一二区| 久久精品一区二区三区不卡牛牛 | 亚洲欧美日韩在线| 亚洲一二三四久久| 欧美日韩视频在线| 亚洲美女精品久久| 一本久道久久综合中文字幕| 欧美激情成人在线| 91久久黄色| 日韩视频在线一区二区三区| 欧美国产综合| 妖精视频成人观看www| 在线一区亚洲| 欧美午夜电影网| 一区二区三区成人精品| 亚洲一区在线免费| 国产精品入口夜色视频大尺度| 宅男噜噜噜66国产日韩在线观看| 亚洲性感激情| 国产欧美精品在线| 久久久精品一区| 欧美成人一品| 99精品国产在热久久| 欧美私人网站| 香蕉久久国产| 欧美激情第1页| 99精品视频网| 国产精品久久网站| 欧美一区国产一区| 欧美成人小视频| 亚洲视频在线观看三级| 国产精品视频网址| 久久米奇亚洲| 夜夜嗨网站十八久久| 欧美淫片网站| 亚洲国产一区在线| 欧美系列精品| 久久久91精品国产一区二区精品| 欧美激情久久久久久| 亚洲一区不卡| 黑人一区二区三区四区五区| 欧美激情一区二区| 亚洲欧美色一区| 欧美高清hd18日本| 亚洲欧美日韩视频一区| 亚洲二区视频在线| 国产精品永久| 欧美高清日韩| 久久gogo国模啪啪人体图| 91久久精品国产91久久性色tv | 亚洲国产你懂的| 国产精品v欧美精品∨日韩| 欧美中文字幕第一页| 日韩网站在线观看| 久久亚洲欧洲| 亚洲免费在线观看| 亚洲欧洲日本国产| 国产视频精品va久久久久久| 欧美精品网站| 久久久噜噜噜久噜久久| 亚洲一区二区三区久久| 91久久夜色精品国产九色| 久久亚洲一区二区| 香蕉国产精品偷在线观看不卡| 亚洲国产欧美日韩精品| 国产一区自拍视频| 国产精品日韩精品| 欧美午夜宅男影院在线观看| 欧美成人免费在线观看| 久久婷婷丁香| 欧美在线中文字幕| 欧美一级久久久| 亚洲一区成人| 在线午夜精品| 日韩视频国产视频| 亚洲激情视频在线播放| 欧美大片一区二区| 久热精品视频在线观看一区| 欧美在线日韩精品| 欧美一区成人| 欧美一区二区三区视频免费播放| 亚洲午夜精品久久久久久浪潮| 最新69国产成人精品视频免费| 狠狠色丁香久久婷婷综合丁香| 国产欧美日韩精品丝袜高跟鞋| 国产精品爱久久久久久久| 欧美日韩国产一区| 欧美巨乳在线观看| 欧美天堂亚洲电影院在线观看| 欧美破处大片在线视频| 欧美激情中文字幕在线| 欧美日韩一级片在线观看| 欧美精品免费看| 欧美日韩专区| 国产老肥熟一区二区三区| 国产乱理伦片在线观看夜一区| 国产美女一区二区| 国产午夜亚洲精品不卡| 韩国av一区二区三区四区| 狠狠色伊人亚洲综合成人| 一区在线免费观看| 亚洲国产精品小视频| 亚洲美女性视频| 亚洲先锋成人| 久久久久久久国产| 欧美成人精品一区二区三区| 欧美激情亚洲自拍| 中国亚洲黄色| 欧美一区二区三区在线播放| 久久免费视频在线观看| 欧美经典一区二区| 国产精品xxxxx| 樱桃国产成人精品视频| 日韩午夜在线播放| 午夜视频一区在线观看| 久久天天躁狠狠躁夜夜av| 欧美高清视频一二三区| 中文国产成人精品| 久久先锋影音av| 国产精品盗摄久久久| 一区二区三区中文在线观看 | 99视频精品免费观看| 亚洲男人av电影| 欧美不卡视频一区发布| 中文在线不卡视频| 久久婷婷av| 国产美女精品| 99re视频这里只有精品| 午夜亚洲影视| 亚洲国产激情| 亚洲欧美日韩精品综合在线观看| 欧美sm重口味系列视频在线观看| 国产精品国产自产拍高清av| 在线播放精品| 欧美一区二区视频观看视频| 亚洲电影在线播放| 香蕉久久夜色精品国产使用方法| 欧美国产视频在线| 一区二区三区在线高清| 性做久久久久久久久| 亚洲国产精品一区二区www| 午夜影视日本亚洲欧洲精品| 欧美乱大交xxxxx| 激情五月***国产精品| 亚洲综合导航| 日韩午夜剧场| 欧美成人午夜77777| 精品99一区二区| 欧美制服第一页|