前言：感觉大佬们只讲了怎么做，没写为什么要这么做 ，不适合我这种蒟蒻理解。所以我写了篇适合蒟蒻食用的题解。

题意

楼梯：左侧齐平，右侧不能往左陷

思路

根据题意，我们先记 $h_{i,j}$，代表 $(i,j)$ 右侧有几个 $1$。

然后，把模板横过来，发现题目就是让我们找最长不下降子串的每一项之和（不过有很多行）。

大体思路有了，现在要实现找每行（横着的）最长不下降子串。

首先，我们从右往左一列一列看（横着的从上到下），记录这格的 $h_{i,j}$ 能从下往上延续多少格，记延续的格数 $l_{i}$（由于每行是单独的，行内计算可以省略 $j$），那么这个 $h_{i,j}$ 能做出 $l_i \times h_{i,j}$ 格贡献（请搭配题图理解）。

然后，我们从上往下（横着的从左到右）遍历，记以当前格为左下角（正看）的楼梯的面积为 $s_i$，$s_i = s_{i - l_i} + l_i \times h_{i,j}$。也就是当前 $h_{i,j}$ 做的贡献加上前面它结束贡献的地方的贡献。以样例为例，$j = 2$ 时，两格的楼梯持续了两个长度，那么 $s_4 = s_2 + l_5 \times h_{5,2}$。

不过直接模拟时间复杂度是 $O((hw)^2)$，会 TLE，我们要优化一下。

我们寻找最长不下降子串的特点是：从右到左，找第一个小于 $h_{i,j}$ 的地方。所以我们能想到用单调栈来优化。单调栈能把时间优化成 $O(hw)$。

我们的思路到此结束，接下来就要开始写代码啦~

代码

#include <bits/stdc++.h>
using namespace std;
vector<vector<bool>> a;
vector<vector<int>> h;	// 以(i,j)为准，右边有多少个1
vector<int> s,l;
// s：对于每个j，以i为左下角的楼梯的最大格数
// l：对于每个j，h[i][j]能向上持续多远（楼梯定义）
int mx;
int main(int argc, char **argv){
	int n,m;
	cin >> n >> m;
	a = vector<vector<bool>>(n + 1,vector<bool>(m + 1));
	h = vector<vector<int>>(n + 1,vector<int>(m + 1));
	s = l = vector<int>(n + 1);
	for (int i = 1;i <= n;i++){
		string s;
		cin >> s;
		for (int j = 1;j <= m;j++){
			a[i][j] = s[j - 1] - '0';
		}
	}
	for (int i = 1;i <= n;i++){
		h[i][m] = a[i][m];
		for (int j = m - 1;j > 0;j--){
			if (a[i][j])	h[i][j] = h[i][j + 1] + 1;
		}
	}
	for (int j = m;j > 0;j--){
		// for (int i = n;i > 0;i--){
		// 	int k = i - 1;
		// 	while (k >= 0 && h[k][j] >= h[i][j])	k--;
		// 	l[i] = i - k;
		// }
		// for (int i = 1;i <= n;i++){
		// 	s[i] = s[i - l[i]] + l[i] * h[i][j];
		// 	mx = max(mx,s[i]);
		// }
		stack<int> st;
		for (int i = n;i > 0;i--){
			l[i] = i;	// 默认能持续到最顶上
			while (!st.empty() && h[st.top()][j] > h[i][j]){
				l[st.top()] = st.top() - i;
				st.pop();
			}
			st.push(i);
		}
		for (int i = 1;i <= n;i++){
			s[i] = s[i - l[i]] + l[i] * h[i][j];
			mx = max(mx,s[i]);
		}
	}
	cout << mx;
	return 0;
}

upd 2025.10.7：纠正一处笔误。