給一$n\times m$矩陣，求最大的子矩陣面積滿足子矩陣內全部都是1
$n,m\leq 200$
這題最直覺的做法就是枚舉一個維度的左右界，可以轉化成最大連續和問題，時間複雜度$\mathcal{O}(n^2m)$
但可以透過建表來得知一格的高(該格以上有多長的連續1)，比如範測:
1
2
3
4
| 0 0 1 1 0
0 1 1 1 1
0 1 1 1 1
0 0 1 0 0
|
可以蓋成:
1
2
3
4
| 0 0 1 1 0
0 1 2 2 1
0 2 3 3 2
0 0 4 0 0
|
這時就可以在單一維度求解了
例如第三列0 2 3 3 2
若取23則面積是$min(2,3)\times (3-2+1)=4$
取24則面積是$min(2,3,3,2)\times (4-2+1)=8$就是答案
處理這個可以用到直方圖求最大面積的手段 - 單調stack
維護一個單調遞增的stack，可以得知每個點所能觸及到(比該點大)的左右界
若這個點比前面的點小，則後面的點的左界肯定不會是前面的點，可以直接pop
pop時，因為該點比前面的點小才會pop，同時可維護被pop點的右界
最後就該點長度*左右界區間
枚舉維度$n$，每一點只會進出stack一次，時間複雜度$\mathcal{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
|
#include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
int arr[201][201], l[201], r[201];
signed main() {
EmiliaMyWife
int n, m, ans = 0;
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> arr[i][j];
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(arr[i][j])
arr[i][j] += arr[i-1][j];
}
arr[i][0] = -INF;
stack<int> cur;
cur.push(0);
for(int j = 1; j <= m; j++) {
while(arr[i][cur.top()] >= arr[i][j])
r[cur.top()] = j, cur.pop();
l[j] = cur.top();
cur.push(j);
}
while(cur.size())
r[cur.top()] = m+1, cur.pop();
for(int j = 1; j <= m; j++)
ans = max(ans, arr[i][j] * (r[j]-l[j]-1));
}
cout << ans;
return 0;
}
|