自动搬运

查看原文

来自洛谷，原作者为

	114514wxy 这个家伙不懒，什么也没有留下

搬运于2025-08-24 22:34:39，当前版本为作者最后更新于2024-03-17 09:51:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

解法很简单：先跑出来满足 YF 条件的 $2 \times 2$ 矩阵，把左上角置为 $1$，最后求全为 $1$ 的矩阵的最大值。

来论证两个东西：全为 1 的矩阵为什么是 Sept 矩阵以及怎么求最大值。

那么第一个，我们不妨以一个 $2 \times 3$ 的矩阵入手，这个矩阵的两个子 $2 \times 2$ 矩阵都是 YF 矩阵。那么就有

$a_{1,1}+a_{2,2} \le a_{1,2}+a_{2,1}$ 和

$a_{1,2}+a_{2,3} \le a_{2,2}+a_{1,3}$。

不等式两边同时相加并消去一下，可以得到

$a_{1,1}+a_{2,3} ≤ a_{2,1}+a_{1,3}$

这个就是满足 YF 的 $2 \times 3$ 矩阵了。

同理也可以推广到更大的矩阵。

第一个证毕。

至于第二个，求解本类 $01$ 矩阵中全为 $0 / 1$ 的矩阵的最大面积可以用悬线法。对于一个 $n \times m$ 的 $01$ 矩阵，具体操作如下：

随着枚举到第 $i$ 行的过程，我们可以对于每一列 $j$ 想象一条悬线，从 $(i,j)$ 的位置向上延伸，直到第一个位置（也就是最靠下的位置）使得 $a_{i-x,j}=0$，其中 $x\in[0,i-1]$。将这条悬线的长记为 $h_j$。接下来，对于本 $h_j$，分别定义

$l_j=\text{max}(k) \text{ 其中}k\in[1,j-1]\text{ 且 } h_{k-1}<h_j$

以及

$r_j=\text{min}(k) \text{ 其中}k\in[j+1,m]\text{ 且 } h_{k+1}<h_j$

这分别意味着这条悬线可以向左或向右“推广到”的距离。

同时，可以认为 $h_0 = h_{m+1} = 0$。

至于计算过程，以 $l_j$ 数组举例，应当先赋值 $l_j=j$，之后尝试向左推广。不难发现，

若 $h_{l_j-1} \ge h_j$

则可以有 $l_j=l_{l_j-1}$

这是因为由上面的条件可以知道：至少一直到 $l_{l_j-1}$ 的位置，对于 $h_k \text{ } k\in[l_{l_j-1},j]$ 都会满足 $h_k \ge h_j$。边界终止条件为 $l_j = 1$。

对于 $r$ 数组的计算同理。

如此，对于一个 $j$，用其上的悬线“推广”出来的矩阵面积就是 $(r_j-l_j+1) \times h_j$。

注意到我们是在缩水过的 $01$ 矩阵上进行的悬线，最终得出的面积应当是上式两个乘数各自 $+1$ 后的值。

代码很简单。

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;

int n,m,a[N][N],ans;
int h[N],l[N],r[N];
bool cd[N][N];

int main(){
	
	cin>>n>>m;
	for(int i=1;i<=n;++i) for(int j=1;j<=m;++j)
	    scanf("%d",&a[i][j]);
	
	--n,--m;
	for(int i=1;i<=n;++i) for(int j=1;j<=m;++j)
	    cd[i][j]=(a[i][j]+a[i+1][j+1]<=a[i][j+1]+a[i+1][j]);
	
	for(int i=1;i<=n;++i){
	    for(int j=1;j<=m;++j)
	        l[j]=r[j]=j,h[j]=(cd[i][j])?h[j]+1:0;
		
	    for(int j=1;j<=m;++j)
		    while(l[j]!=1&&h[l[j]-1]>=h[j]) l[j]=l[l[j]-1];
	    for(int j=m;j>=1;--j)
		    while(r[j]!=m&&h[r[j]+1]>=h[j]) r[j]=r[r[j]+1];
		
	    for(int j=1;j<=m;++j)
		    ans=max(ans,(r[j]-l[j]+2)*(h[j]+1));
	}
	cout<<ans<<endl;
	return 0;
}