【ZJOI2007】棋盘制作

痛定思痛。 2021-12-12 09:09 221阅读 0赞

### Description ###

给定一个01矩阵，求出最大的正方形子矩阵和最大长方形子矩阵，并保证取出的矩阵中的元素都为0/1

### Solution ###

为了使题目变成上述表述的形式，我们首先将读入的矩阵的部分元素xor1，使其变成一般形式

之后，这道题变成了两道题的合体：洛谷P2701巨大的牛棚与P4147玉蟾宫

我们分开讨论，对于最大正方形，我们设计一个dp，定义f\[i\]\[j\]表示以(i, j)为右下角的最大正方形的边长，状态转移方程为

f\[i\]\[j\] = min(f\[i - 1\]\[j - 1\], f\[i - 1\]\[j\], f\[i\]\[j - 1\]) + 1

那么答案也是显然的，ans = max(f\[i\]\[j\] \* f\[i\]\[j\])

对于最大矩形，我们使用单调栈求解，具体步骤请见[这里][Link 1]

注意，本题要求求出最大正方形与矩形，所以我们要将这两个算法对0/1矩阵各做一遍，时间复杂度为O(n^2)

### Code ###

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <iostream>
     2 #include <cstdio>
     3 #include <cstring>
     4 using namespace std;
     5 int n, m;
     6 int a[2010][2010], vis[2010][2010];
     7 int ans1, f1[2010][2010], f2[2010][2010], ans2, b[2010]; 
     8 int s[2010], p, w[2010];
     9 int main() { 
    10     scanf("%d%d", &n, &m);
    11     for (register int i = 1; i <= m; ++i) vis[1][i] = vis[1][i - 1] ^ 1;
    12     for (register int i = 2; i <= n; ++i)
    13         for (register int j = 1; j <= m; j++)
    14             vis[i][j] = vis[i - 1][j] ^ 1;
    15     for (register int i = 1; i <= n; ++i)
    16         for (register int j = 1; j <= m; ++j) {
    17             scanf("%d", &a[i][j]);
    18             if(!vis[i][j]) a[i][j] ^= 1;
    19         }
    20     for (register int i = 1; i <= n; ++i)
    21         for (register int j = 1; j <= m; ++j)
    22             if (a[i][j]) {
    23                 f1[i][j] = min(f1[i - 1][j - 1], min(f1[i - 1][j], f1[i][j - 1])) + 1;
    24                 ans1 = max(ans1, f1[i][j]);
    25             }
    26     for (register int i = 1; i <= n; ++i)
    27         for (register int j = 1; j <= m; ++j)
    28             if (!a[i][j]) {
    29                 f2[i][j] = min(f2[i - 1][j - 1], min(f2[i - 1][j], f2[i][j - 1])) + 1;
    30                 ans1 = max(ans1, f2[i][j]);
    31             }
    32     printf("%d\n", ans1 * ans1);
    33     for (register int i = 1; i <= n; ++i) {
    34         for (register int j = 1; j <= m; ++j)
    35             b[j] = a[i][j] ? b[j] + 1 : 0;
    36         p = 0;
    37         for (register int j = 1; j <= m + 1; ++j) {
    38             if (b[j] > s[p]) s[++p] = b[j], w[p] = 1;
    39             else {
    40                 int tot = 0;
    41                 while (b[j] < s[p]) {
    42                     tot += w[p];
    43                     ans2 = max(ans2, s[p] * tot);
    44                     p--;
    45                 }
    46                 s[++p] = b[j];
    47                 w[p] = tot + 1;
    48             }
    49         }
    50     }
    51     for (register int i = 1; i <= n; ++i) {
    52         for (register int j = 1; j <= m; ++j)
    53             b[j] = a[i][j] == 0 ? b[j] + 1 : 0;
    54         p = 0;
    55         for (register int j = 1; j <= m + 1; ++j) {
    56             if (b[j] > s[p]) s[++p] = b[j], w[p] = 1;
    57             else {
    58                 int tot = 0;
    59                 while (b[j] < s[p]) {
    60                     tot += w[p];
    61                     ans2 = max(ans2, s[p] * tot);
    62                     p--;
    63                 }
    64                 s[++p] = b[j];
    65                 w[p] = tot + 1;
    66             }
    67         }
    68     }
    69     printf("%d\n", ans2);
    70     return 0;
    71 }

AC Code

转载于:https://www.cnblogs.com/shl-blog/p/11142878.html

[Link 1]: https://www.cnblogs.com/shl-blog/p/10885867.html
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211211/b03c12d8d48243be9075a45f6a3b4aed.png