题解：P7958 [COCI2014-2015#6] NEO

· · 题解

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

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

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

$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;
}