gzwzm06

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

:: 管理 ::

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

<

2025年11月

>

日

一

二

三

四

五

六

26

27

28

29

30

31

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

1

2

3

4

5

6

常用鏈接

留言簿(3)

隨筆檔案

2009年5月 (1)

文章分類

文章檔案

搜索

最新評論

1.?re: Pku 2774--Long Long Message（后綴樹）
求教大牛，那個Lt屬性是記錄什么的
--dereky
2.?re: POJ 2481(樹狀數組)
@gzwzm06
哦，實在是不好意思，確實是那個地方，現在過了，謝謝了啊。
--Klion
3.?re: POJ 2481(樹狀數組)
你再檢查下，cc[j].m_e == cc[j].m_e這個條件肯定是真的，沒有意義吧
--gzwzm06
4.?re: POJ 2481(樹狀數組)
@gzwzm06
兩個相同一起比較也就是兩個區間是一樣的，起點和終點是相同的，和您的第80行比較的應該是一樣的吧？
--Klion
5.?re: POJ 2481(樹狀數組)
評論內容較長,點擊標題查看
--gzwzm06

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 巫閱讀(659) 評論(3) 編輯收藏引用所屬分類: DP

只有注冊用戶登錄后才能發表評論。


相關文章: 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 管理

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