题解
这个题类似于最大柱状图面积的升级版，只需要枚举每一行为底，从之前一行的每一条柱的高度推出这一行的高度，然后用单调栈计算即可。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
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
char s[50][50];
int n, st[50], w[50], top, h[50] = {0};
void init(){
scanf("%s", s[0]);
n = strlen(s[0]);
for (int i = 1; i < n; ++i)
scanf("%s", s[i]);
}
void solve(){
int ans = 0;
for (int i = 0, cur = 0; i < n; ++i){
if(s[0][i] == '1') h[i] = 1, cur++, ans = max(ans, cur);
else cur = 0, h[i] = 0;
}
for (int i = 1; i < n; ++i){
for (int j = 0; j < n; ++j){
if(s[i][j] == '1') h[j]++;
else h[j] = 0;
}
top = 0;
for (int j = 0; j <= n; ++j){
int curw = 0;
while(top && st[top] >= h[j])
curw += w[top], ans = max(ans, curw * st[top]), top--;
w[++top] = curw + 1, st[top] = h[j];
}
}
printf("%d\n", ans);
}
int main(){
int T = read();
while(T--){
init();
solve();
if(T) printf("\n");
}
return 0;
}