[ZJOI2007] 棋盘制作

发表于 | 分类于 >
字数统计 : 596   |   阅读时长 ≈ 3 mins.

题目

链接

[ZJOI2007]棋盘制作

题意简述

给定一个长度为 的矩形，求黑白相间的最大正方形和矩形。

思路

主要问题是把黑白相间的格子转换成全黑格。
注意到黑白相间，所以对不相邻的格子取反即可。
这样就转换成最大化子矩形问题。
注意这里并没有严格意义上的障碍点，所以要以黑和白为障碍点各跑一次。

最大化子矩形

模板。（摸你赛的时候我还不会
时间复杂度： $O(n^{2})$ 。
预期得分： $(100)$。

代码

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
#include <bits/stdc++.h>
#define REG register
#define IN inline
#define For(x,y,z) for (REG int (x) = (y); (x) <= (z); ++(x))
#define FOR(x,y,z) for (REG int (x) = (y); (x) <  (z); ++(x))
const int kmax_num = 2e3 + 10, kmax_int = INT_MAX, kmod = 1e6;

int n, m;

int f[kmax_num][kmax_num], t[kmax_num], l[kmax_num], r[kmax_num];

int main() {
    std::cin >> n >> m;

    REG int x, y;
    For(i,1,n)  For(h,1,m)  {
        std::cin >> f[i][h];
        if(!((i + h) % 2))  f[i][h] = !f[i][h];
    }

    For(i,1,m)  r[i] = m + 1;

    REG char tem;
    REG int num, ans1 = 0, ans2;
    For(i,1,n)  {
        For(h,1,m)  {
            t[h] = !f[i][h] ? t[h] + 1 : 0;
        }

        num = 0;
        For(h,1,m)
            if(!f[i][h])    l[h] = std::max(l[h], num);
            else        l[h] = 0, num = h;

        num = m+ 1;
        for(REG int h = m; h; --h)
            if(!f[i][h])    r[h] = std::min(r[h], num);
            else        r[h] = m + 1, num = h;

        For(h,1,m)
            ans1 = std::max(ans1, (r[h] - l[h] - 1) * t[h]),
            ans2 = std::max(ans2, std::min(r[h] - l[h] - 1, t[h]) * std::min(r[h] - l[h] - 1, t[h]));
    }

    memset(t, 0, sizeof(t));
    memset(l, 0, sizeof(l));
    memset(r, 0, sizeof(r));

    For(i,1,m)  r[i] = m + 1;
    For(i,1,n)  {
        For(h,1,m)  {
            t[h] = f[i][h] ? t[h] + 1 : 0;
        }

        num = 0;
        For(h,1,m)
            if(f[i][h])    l[h] = std::max(l[h], num);
            else        l[h] = 0, num = h;

        num = m + 1;
        for(REG int h = m; h; --h)
            if(f[i][h])    r[h] = std::min(r[h], num);
            else        r[h] = m + 1, num = h;

        For(h,1,m)
            ans1 = std::max(ans1, (r[h] - l[h] - 1) * t[h]),
            ans2 = std::max(ans2, std::min(r[h] - l[h] - 1, t[h]) * std::min(r[h] - l[h] - 1, t[h]));
    }

    printf("%d\n%d\n", ans2, ans1);
    return 0;
}

杂项