gzwzm06

C++博客 :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合

:: 管理 ::

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(樹狀數(shù)組)
@gzwzm06
哦，實在是不好意思，確實是那個地方，現(xiàn)在過了，謝謝了啊。
--Klion
3.?re: POJ 2481(樹狀數(shù)組)
你再檢查下，cc[j].m_e == cc[j].m_e這個條件肯定是真的，沒有意義吧
--gzwzm06
4.?re: POJ 2481(樹狀數(shù)組)
@gzwzm06
兩個相同一起比較也就是兩個區(qū)間是一樣的，起點和終點是相同的，和您的第80行比較的應該是一樣的吧？
--Klion
5.?re: POJ 2481(樹狀數(shù)組)
評論內容較長,點擊標題查看
--gzwzm06

Pku 3494--Largest Submatrix of All 1’s(路徑壓縮)

1

#include <cstdio>
2

#include <cstring>
3

4

const int MAXN = 4008 ;
5

const int SIZE = 2003 ;
6

7

int left[SIZE], right[SIZE] ;
8

int height[SIZE] ;
9

10

int GetMaxArea(const int& len)
11

{
12

int i , j , temp , maxArea ;
13

maxArea = 0 ;
14

15

height[0] = height[len + 1] = -1 ;
16

17

18

for ( i = 1 ; i <= len ; ++i )
19

{
20

for ( j = i - 1 ; ; j = left[j] )
21

{
22

if ( height[j] < height[i] )
23

{
24

left[i] = j ;
25

break ;
26

}
27

}
28

}
29

30

for ( i = len ; i > 0 ; --i )
31

{
32

for ( j = i + 1 ; ; j = right[j] )
33

{
34

if ( height[j] < height[i] )
35

{
36

right[i] = j ;
37

break ;
38

}
39

}
40

}
41

42

for ( i = 1 ; i <= len ; ++i )
43

{
44

if ( height[i] != height[i - 1] )
45

{
46

temp = height[i] * (right[i] - left[i] - 1) ;
47

48

if ( temp > maxArea )
49

maxArea = temp ;
50

}
51

}
52

53

return maxArea ;
54

55

}
56

57

int main()
58

{
59

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

61

int row , col , i , j ;
62

int ans , temp , num ;
63

char strData[MAXN] ;
64

65

while ( scanf("%d %d", &row, &col) != EOF )
66

{
67

getchar() ;
68

gets(strData) ;
69

for ( j = 1 ; j <= col ; ++j )
70

{
71

height[j] = strData[(j - 1) * 2] - '0' ;
72

}
73

74

ans = GetMaxArea(col) ;
75

76

for ( i = 1 ; i < row ; ++i )
77

{
78

gets(strData) ;
79

80

for ( j = 1 ; j <= col ; ++j )
81

{
82

num = strData[(j - 1) * 2] - '0' ;
83

if ( 0 == num ) {
84

height[j] = 0 ;
85

}
86

else if ( 1 == num ) {
87

height[j]++ ;
88

}
89

}
90

91

temp = GetMaxArea(col) ;
92

93

if ( temp > ans )
94

ans = temp ;
95

}
96

97

printf("%d\n", ans) ;
98

}
99

return 0 ;
100

}

posted on 2009-03-06 11:10 巫閱讀(262) 評論(0) 編輯收藏引用所屬分類: DP

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


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

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