P4147. 玉蟾宫

发表于 分类于 阅读次数： Waline： 本文字数： 935 阅读时长 ≈ 3 分钟

考点

  • 单调栈
  • 最大子矩形

题解

见思路

思路

以下图为例：

单调栈

但凡是个矩形，必须有个底、有个高；那么以行为单位处理，统计以第k行为底边的矩形。

假设当前统计以第4行为底的矩形，那么例图可以转换如下所示。

实际上就是在这个”山“形状中寻找一个极大的矩形。

考虑当高度单调递增时，每一列都能向右延伸至边界：

一旦破坏了单调性，每列向右扩展得到的最大矩形如下：

设h[i][j]代表以第i行为底，第j列从底往上最大连续空格的数量（就是矩形的高）

故而得到下列处理流程：

  1. 每个第i行都用单调栈维护一个h[i][j]单调递增的序列；

  2. 若待进栈j的高度小于等于栈顶top的高度，

    代表以top的宽度为左边，以top的高度向右扩展的矩阵到头了；

  3. 统计以top的宽度为左边，以top的高度向右扩展的矩阵宽度，

    即当前矩阵宽度sum = 上一个矩阵宽度 + 当前top的宽度。

  4. 以top的宽度为左边，以top的高度向右扩展的最大矩阵面积，

    显然等于sum * h[i][st[top]]

以上述为例，当前top的高度为5，待进栈j的高度为2；

根据当前矩阵宽度sum = 上一个矩阵宽度 + 当前top的宽度可知，

sum = 0（默认值）+ top的宽度（默认为1）= 1

也就是说，以top的宽度为左边，以top的高度向右最大扩展的矩形的宽度为1。

随后弹出top，此刻top的高度为3，依旧大于等于j的高度2

sum = 1 + top的宽度 = 2

再弹出top，此刻top的高度为2，依旧大于等于2

sum = 2 + top的宽度 = 3

弹出top后，此时top的高度1和待进栈j的高度2，都可以扩展sum的宽度

那么令待进栈j的宽度 = sum + j自身宽度 = 4，再入栈即可

原本在栈内的元素不必动它，它们会和某个top一并处理

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 50;
char ch[maxn][maxn];
int n, m, ans, st[maxn];

struct node {
  int h_, w_;
} a[maxn][maxn];

void f(int row) {
  int sum = 0, top = 0;
  for (int j = 1; j <= m; ++j) {
    sum = 0;
    while (top && a[row][st[top]].h_ >= a[row][j].h_) {
      sum += a[row][st[top]].w_;
      ans = max(ans, sum * a[row][st[top--]].h_);
    }
    st[++top] = j, a[row][j].w_ += sum;
  }
  sum = 0;
  while (top) {
    sum += a[row][st[top]].w_;
    ans = max(ans, sum * a[row][st[top--]].h_);
  }
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      cin >> ch[i][j];
      a[i][j].w_ = 1;
      if (ch[i][j] == 'F') a[i][j].h_ = a[i - 1][j].h_ + 1;
    }
  }
  for (int i = 1; i <= n; ++i) f(i);
  cout << 3 * ans;
  return 0;
}

悬线法

直接上《深进》的图

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 50;
char c[maxn][maxn];
int n, m, ans, h[maxn][maxn], l[maxn][maxn], r[maxn][maxn];

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      cin >> c[i][j];
      h[i][j] = 1, l[i][j] = r[i][j] = j;
    }
    for (int j = 1; j < m; ++j) {
      if (c[i][j] == 'F' && c[i][j + 1] == 'F') l[i][j + 1] = l[i][j];
    }
    for (int j = m; j >= 2; --j) {
      if (c[i][j] == 'F' && c[i][j - 1] == 'F') r[i][j - 1] = r[i][j];
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      if (c[i][j] == 'F') {
        if (c[i - 1][j] == 'F') {
          h[i][j] = h[i - 1][j] + 1;
          l[i][j] = max(l[i][j], l[i - 1][j]);
          r[i][j] = min(r[i][j], r[i - 1][j]);
        }
        ans = max(ans, (r[i][j] - l[i][j] + 1) * h[i][j]);
      }
    }
  }
  cout << ans * 3;
  return 0;
}