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

<center id="somag"><acronym id="somag"></acronym></center>

<rt id="somag"><delect id="somag"></delect></rt>

<button id="somag"><input id="somag"></input></button>

<rt id="somag"><tr id="somag"></tr></rt>

<abbr id="somag"><source id="somag"></source></abbr><button id="somag"><strong id="somag"></strong></button>

<abbr id="somag"><tbody id="somag"></tbody></abbr>

<rt id="somag"><delect id="somag"></delect></rt>

gzwzm06

C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合

:: 管理 ::

1 隨筆 :: 52 文章 :: 17 評論 :: 0 Trackbacks

POJ 2559--Largest Rectangle in a Histogram(棧模擬)

1

//棧模擬---157ms
2

//更好的方法，也許是DP吧
3

4

#include <cstdio>
5

6

const int SIZE = 100001 ;
7

8

struct STACK
9

{
10

__int64 ht ;
11

int pos ;
12

} ;
13

14

STACK stack[SIZE] ;
15

int top ;
16

17

int N ;
18

__int64 height[SIZE] ;
19

20

__int64 GetMaxArea()
21

{
22

__int64 ans , temp ;
23

int i ;
24

25

top = 0 ;
26

27

stack[top].ht = height[0] ;
28

stack[top].pos = 0 ;
29

ans = height[0] ;
30

height[N] = 0 ;
31

32

for ( i = 1 ; i <= N ; ++i )
33

{
34

if ( height[i] <= stack[top].ht )
35

{
36

while ( top >= 0 && height[i] <= stack[top].ht )
37

{
38

temp = stack[top].ht * (i - stack[top].pos) ;
39

40

if ( temp > ans )
41

ans = temp ;
42

43

top-- ;
44

}
45

top++ ;
46

stack[top].ht = height[i] ;
47

}
48

else {
49

stack[++top].ht = height[i] ;
50

stack[top].pos = i ;
51

}
52

}
53

54

return ans ;
55

}
56

57

int main()
58

{
59

// freopen("1.txt", "r", stdin) ;
60

61

int i ;
62

63

while ( scanf("%d", &N) && N != 0 )
64

{
65

for ( i = 0 ; i < N ; ++i )
66

{
67

scanf("%I64d", &height[i]) ;
68

}
69

70

__int64 ans = GetMaxArea() ;
71

72

printf("%I64d\n", ans) ;
73

}
74

75

return 0 ;
76

}

posted on 2009-03-05 23:17 巫閱讀(637) 評論(3) 編輯收藏引用所屬分類: DP

評論

# re: POJ 2559--Largest Rectangle in a Histogram(棧模擬)[未登錄] 2009-07-02 12:26 xc

如果輸入的測試數據是 2 1 10
你的代碼輸出是 1
可正確的輸出應該是 10 回復更多評論

# re: POJ 2559--Largest Rectangle in a Histogram(棧模擬)[未登錄] 2009-07-02 12:32 xc

48 else {
if (height[i] > ans)
ans = height[i] ;
49 stack[++top].ht = height[i] ;
50 stack[top].pos = i ;
51 }
回復更多評論

# re: POJ 2559--Largest Rectangle in a Histogram(棧模擬)[未登錄] 2009-07-02 12:39 xc

不好意思沒看見“ height[N] = 0 ;”這句話回復更多評論

刷新評論列表

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: 7th GDCPC Problem G: Black Jack ZOJ 3187--Inviting Friends zoj 3201 Tree of tree POJ 3211 Washing Clothes POJ 3254 Corn Fields POJ 3670 Eating Together(最長非遞增（非遞減）子序列) POJ 3661-Running Pku 3494--Largest Submatrix of All 1’s(路徑壓縮) PKU 1964--City Game(棧模擬) POJ 2559--Largest Rectangle in a Histogram(棧模擬)

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

99久久夜色精品国产网站| 一级a性色生活片久久无少妇一级婬片免费放| 久久综合九色综合久99| 色综合合久久天天给综看| 亚洲乱码精品久久久久..| 久久免费精品一区二区| 性欧美大战久久久久久久| 国产亚洲精品自在久久| 中文成人无码精品久久久不卡| 人妻久久久一区二区三区| 国内精品久久久久| 亚洲国产成人久久综合一区77| 欧美国产成人久久精品| 99久久精品国产一区二区三区| 2020久久精品亚洲热综合一本| 久久国产精品成人免费| 亚洲av伊人久久综合密臀性色 | 久久久久久伊人高潮影院| 国产精品天天影视久久综合网| 久久精品成人| 久久精品aⅴ无码中文字字幕重口| 99久久国产综合精品五月天喷水 | 精品久久人人做人人爽综合 | 色婷婷综合久久久中文字幕| 国内精品久久久久久不卡影院| 久久久一本精品99久久精品88| 久久精品极品盛宴观看| 亚洲性久久久影院| 久久九九免费高清视频| 93精91精品国产综合久久香蕉 | 亚洲精品无码久久久| 久久国产免费直播| 久久精品国产黑森林| 丰满少妇人妻久久久久久4| 狠狠色丁香婷婷久久综合不卡| 色欲av伊人久久大香线蕉影院| 久久综合视频网站| 亚洲欧美成人久久综合中文网| 久久亚洲高清综合| 久久综合九色综合欧美就去吻| 亚洲第一永久AV网站久久精品男人的天堂AV |

<rt id="awyci"><acronym id="awyci"></acronym></rt>

<code id="awyci"><acronym id="awyci"></acronym></code><sup id="awyci"><input id="awyci"></input></sup>

<cite id="awyci"></cite>

<rt id="awyci"><delect id="awyci"></delect></rt>

<table id="awyci"><dl id="awyci"></dl></table>