题目描述
（看不清图片可以右击图片-> 复制图片地址 ->浏览器新开一个标签页，粘贴此地址就可看大图
（也可以右击图片-> 在新标签页打开图片
题解
听师哥讲得才明白怎么做， 我好菜啊~！
单调栈的应用
把题目中矩阵拆开看， 看成以第i行为底的直方图， 然后暴力这i行， 根据单调栈求即可。
可以转化成这题来做： 点此
有几个小问题需要注意：
- 以第i行的矩阵可以由第i-1行求出
- 添加的时候需要注意， 不仅仅要把所求的添加上， 还要加上原矩阵 宽减一 乘以 高 和 宽 乘以 高减一。
ac代码：
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
88
89
90
91
92
93
94
95
96
97
98
|
#include <iostream>
#include <stack>
#include "algorithm"
#include "cstdio"
#include "queue"
#include "set"
#include "cstring"
#include "string"
#include "map"
#include "vector"
#include "math.h"
#include "utility"
#define esp 1e-6
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 5;
struct node{
int height;
int width;
node(){
height = 0;
width = 0;
}
};
int n, m;
int ans1, ans2;
stack <node> st;
string s;
int a[1003][1003];
void max2(int a){
if (ans1 < a){
ans2 = ans1;
ans1 = a;
}
else if (ans2 < a)
ans2 = a;
}
void solotion(int x[]){
node a;
for (int i = 1; i <= m + 1; i++){
if (i <= m)
a.height = x[i];
else
a.height = -1;
a.width = i;
while(!st.empty() && st.top().height >= a.height) {
int x1 = st.top().height, x2 = i - st.top().width;
max2(x1 * x2);
max2(x1 * (x2 - 1));
max2((x1 - 1) * x2);
a.width = st.top().width;
st.pop();
}
st.push(a);
}
}
int main(){
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; i++){
cin >> s;
for (int j = 1; j <= m; j++){
if (i == 1)
a[i][j] = s[j - 1] - '0';
else{
if (s[j - 1] == '1')
a[i][j] = a[i - 1][j] + 1;
else
a[i][j] = 0;
}
}
}
for (int i = 1; i <= n; i++)
solotion(a[i]);
cout << ans2 << "\n";
return 0;
}
|
1
| 恰似你一低头的温柔，较弱水莲花不胜寒风的娇羞， 我的心为你悸动不休。
|