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

            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.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],值最大的那個就是所求的最大高度了。
            久久久久久国产精品无码超碰| 国产日韩欧美久久| 久久人人爽人人爽人人爽| 人妻无码精品久久亚瑟影视| 精品无码久久久久久午夜| 久久综合丁香激情久久| 久久国产精品免费| 91久久婷婷国产综合精品青草| 四虎影视久久久免费| 久久777国产线看观看精品| 欧美精品国产综合久久| 久久久久久久尹人综合网亚洲| 欧美午夜A∨大片久久| 国产精品久久国产精品99盘| 日本久久中文字幕| 亚洲伊人久久大香线蕉苏妲己| 国内精品久久久久久99| 亚洲国产香蕉人人爽成AV片久久 | 一级a性色生活片久久无少妇一级婬片免费放| 久久久WWW成人免费精品| 久久久久女教师免费一区| 粉嫩小泬无遮挡久久久久久| 中文国产成人精品久久亚洲精品AⅤ无码精品| 久久精品人人做人人妻人人玩| 日本WV一本一道久久香蕉| 久久久亚洲精品蜜桃臀| 久久亚洲国产成人精品无码区| 国产欧美一区二区久久| AV无码久久久久不卡蜜桃 | 99国产精品久久| 久久精品无码午夜福利理论片| 久久国产欧美日韩精品免费| 老司机午夜网站国内精品久久久久久久久| 国产V综合V亚洲欧美久久| 色综合久久久久综合体桃花网| 亚洲精品tv久久久久久久久| 欧美日韩精品久久久免费观看| 免费一级做a爰片久久毛片潮| 日批日出水久久亚洲精品tv| 色婷婷综合久久久久中文字幕 | 久久综合给合久久狠狠狠97色|