解題區/解題區 - UVa

UVa 11871 - New Land

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

題目給定在 n * m 的格子中，以及一些障礙物，求一個最大空白矩形。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
2
5 7
5 0 1 2 1 2 1
3 0 5 1 1
3 1 1 5 1
4 0 1 1 4 1
4 1 2 3 1 1
3 3
2 0 2 1
2 1 1 2
3 1 1 1 1

Sample Output

1
2
Case 1: 12
Case 2: 3

Solution

帶入單調堆。

線性時間 O(NM) 完成。紀錄每一列的向左拓展最寬為何，然後對於每一列(假設它是矩形的最右側的邊上)找到最大矩形。

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <string.h>
#define maxL ((2048*2048)>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
using namespace std;
int mark[maxL];
inline int readchar() {
    const int N = 1048576;
    static char buf[N];
    static char *p = buf, *end = buf;
    if(p == end) {
        if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
        p = buf;
    }
    return *p++;
}
inline int ReadInt(int *x) {
    static char c, neg;
    while((c = readchar()) < '-')    {if(c == EOF) return 0;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = readchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
// http://mypaper.pchome.com.tw/zerojudge/post/1326159411
int solve(int n, int h[]) {
    int ret = 0;
    int i, height;
    stack< pair<int, int> > stk;// <height, position>
    pair<int, int> e;
    stk.push(make_pair(-1, 0));
    h[n] = 0;// visual height.
    for(i = 0; i <= n; i++) {
        height = h[i];
        e = make_pair(height, i);
        while(height < stk.top().first) {
            e = stk.top(), stk.pop();
            ret = max(ret, (i - e.second) * e.first);
        }
        if(height > stk.top().first)
            stk.push(make_pair(height, e.second));
    }
    return ret;
}    
int n, m, h[2048];
int main() {
    int k, c, x, cases = 0, testcase;
    ReadInt(&testcase);
    while(testcase--) {
    	ReadInt(&n);
    	ReadInt(&m);
    	memset(mark, 0, sizeof(mark));
    	memset(h, 0, sizeof(h));
        for(int i = 0; i < n; i++) {
        	ReadInt(&k);
        	ReadInt(&c);
        	int pos = 0;
            for(int j = 0; j < k; j++) {
            	ReadInt(&x);
                c = !c;
                if(c) {
            		while(x--)
            			SET(i * 2048 + pos), pos++;
            	} else {
            		pos += x;
            	}
            }
        }
        int ret = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
            	if(GET(j * 2048 + i))
            		h[j]++;
            	else
            		h[j] = 0;
            }
            ret = max(ret, solve(n, h));
        }
        printf("Case %d: %d\n", ++cases, ret);
    }
    return 0;
}