久久久久人妻精品一区,avtt天堂网久久精品,久久精品国产第一区二区三区

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

//棧模擬---157ms
2

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

#include <cstdio>
5

const int SIZE = 100001 ;
7

struct STACK
9

{
10

__int64 ht ;
11

int pos ;
12

} ;
13

STACK stack[SIZE] ;
15

int top ;
16

int N ;
18

__int64 height[SIZE] ;
19

__int64 GetMaxArea()
21

{
22

__int64 ans , temp ;
23

int i ;
24

top = 0 ;
26

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

stack[top].pos = 0 ;
29

ans = height[0] ;
30

height[N] = 0 ;
31

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

if ( temp > ans )
41

ans = temp ;
42

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

return ans ;
55

}
56

int main()
58

{
59

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

int i ;
62

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

{
65

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

{
67

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

}
69

__int64 ans = GetMaxArea() ;
71

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

}
74

return 0 ;
76

}

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

只有注冊用戶登錄后才能發表評論。
【推薦】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 管理

gzwzm06

常用鏈接

留言簿(3)

隨筆檔案

文章分類

文章檔案

搜索

最新評論

評論