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

            為生存而奔跑

               :: 首頁 :: 聯系 :: 聚合  :: 管理
              271 Posts :: 0 Stories :: 58 Comments :: 0 Trackbacks

            留言簿(5)

            我參與的團隊

            搜索

            •  

            積分與排名

            • 積分 - 328615
            • 排名 - 74

            最新評論

            閱讀排行榜

            評論排行榜

            【題目大意】給定n個連續的長度為1的矩形的高度h(1<=n<=100000,0<=hi<=1000000000),問你其中能構成的最大矩形的面積是多少。
            【思路】很顯然,用DP。但關鍵是怎樣表示狀態,一開始想用一個二維數組min[][]表示從i~j的最小高度,面積就等于min[i][j]*(j-i+1)。但很不幸,根據題目給定的n的范圍,這個二維數組根本無法創建。:(
                后來從論壇上得到提示,因為對于圖中的某個面積最大的矩形,必然有一個最低的高度h[k],即矩形的高等于h[k],以第k塊矩形的高度,最左邊可以到達這個矩形的左邊,最右邊可以到達這個矩形的右邊。所以,可以以每塊矩形進行擴展,求出最左邊和最右邊(即兩邊的高度都大于等于這塊的高度),得出面積s[i],這樣就可求出最大的s[i]了。
            PKU 2559
            posted on 2009-08-19 15:59 baby-fly 閱讀(726) 評論(1)  編輯 收藏 引用 所屬分類: Algorithm

            Feedback

            # re: 【最大子矩陣】PKU 2559 Largest Rectangle in a Histogram 2010-07-30 11:13 429298105
            難道不會超時嗎?
              回復  更多評論
              

            久久青草国产精品一区| 久久福利片| 天堂无码久久综合东京热| 久久精品国产亚洲av瑜伽| 日本精品久久久久久久久免费| 亚洲国产成人久久一区久久| 亚洲日韩中文无码久久| 亚洲天堂久久精品| 亚洲国产欧洲综合997久久| 久久亚洲国产午夜精品理论片| 久久精品国产精品亚洲艾草网美妙| 久久久国产视频| 久久国产成人午夜AV影院| 亚洲精品乱码久久久久66| 国产午夜精品久久久久九九电影| 欧美日韩精品久久久免费观看| 久久伊人色| 久久久久久久久久免免费精品 | 一本久久a久久精品vr综合| 国产人久久人人人人爽| 国内精品综合久久久40p| 久久中文娱乐网| 久久精品亚洲一区二区三区浴池 | 久久精品国产亚洲欧美| 日韩精品久久久肉伦网站| 超级碰碰碰碰97久久久久| 国产无套内射久久久国产| 94久久国产乱子伦精品免费 | 久久99精品国产麻豆蜜芽| 久久综合精品国产二区无码| 国产香蕉久久精品综合网| 久久青青草原精品影院| 国内精品久久久久久野外| 久久久久亚洲av无码专区| 日本久久久久亚洲中字幕| A级毛片无码久久精品免费| 久久久精品人妻一区二区三区蜜桃| 99精品国产免费久久久久久下载| 久久久久亚洲AV成人网人人软件| 日本久久久久久中文字幕| 国产精品九九久久免费视频 |