久久性精品,国内精品久久久久国产盗摄,国产精品岛国久久久久

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) 評(píng)論(3) 編輯收藏引用所屬分類: DP

評(píng)論

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

如果輸入的測(cè)試數(shù)據(jù)是 2 1 10
你的代碼輸出是 1
可正確的輸出應(yīng)該是 10 回復(fù) 更多評(píng)論

# 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 }
回復(fù) 更多評(píng)論

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

不好意思沒看見“ height[N] = 0 ;”這句話回復(fù) 更多評(píng)論

刷新評(píng)論列表

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: 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(最長(zhǎng)非遞增（非遞減）子序列) POJ 3661-Running Pku 3494--Largest Submatrix of All 1’s(路徑壓縮) PKU 1964--City Game(棧模擬) POJ 2559--Largest Rectangle in a Histogram(棧模擬)

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

gzwzm06

常用鏈接

留言簿(3)

隨筆檔案

文章分類

文章檔案

搜索

最新評(píng)論

評(píng)論