变异 [单调栈]

$变异$变异

$Description$Description

$Solution$Solution

首先要知道,
$对于两个相嵌的2\ast 2矩阵,若两个都满足变异条件,则拼起来也满足变异条件.$对于两个相嵌的2∗2矩阵,若两个都满足变异条件,则拼起来也满足变异条件.

于是枚举所有 $2\ast 2$2∗2 矩阵,

• 若满足条件, 则将其中的数字赋为 $0$0, 否则赋为 $1$1.
• $0$0 可以将 $1$1 覆盖

$两个镶嵌的2\ast 2矩阵得出的是2\ast 3矩阵,赋值时这个2\ast 3矩阵会转化为两个0,相当于只在格点上放置,这样在应用以下方法时可以保证正确性.$两个镶嵌的2∗2矩阵得出的是2∗3矩阵,赋值时这个2∗3矩阵会转化为两个 0,相当于只在格点上放置,这样在应用以下方法时可以保证正确性.

得到 $R\ast S$R∗S 的 $0,1$0,1矩阵,
记录每个数上方 最长 $0$0 序列的长度 $Up\left[i\right]\left[j\right]$Up[i][j],
对于每一行, 单调栈 从左向右寻找最大 $0$0 矩阵,

如何使用单调栈寻找最大 $0$0 矩阵 ?

求出每个数的 $Ld\left[\right]$Ld[], $Rd\left[\right]$Rd[].
设当前数编号为 $i$i, 则
$Ans=max\left\{\right(Up\left[i\right]\left[j\right]+1)\ast (Rd\left[j\right]-Ld\left[j\right]-1+1\left)\right\},i\in [1,M]$Ans = max{(Up[i][j]+1)∗(Rd[j]−Ld[j]−1+1)},    i∈[1,M]

$Code$Code

#include<bits/stdc++.h>
#define reg register

int read(){
        char c;
        int s = 0, flag = 1;
        while((c=getchar()) && !isdigit(c))
                if(c == '-'){ flag = -1, c = getchar(); break ; }
        while(isdigit(c)) s = s*10 + c-'0', c = getchar();
        return s * flag;
}

const int maxn = 1006;

int N;
int M;
int Ans;
int A[maxn][maxn];
int B[maxn][maxn];
int Up[maxn][maxn];
int Rd[maxn];
int Ld[maxn];

bool chk(int i, int j){ return B[i][j]+B[i+1][j+1] <= B[i][j+1]+B[i+1][j]; }

int main(){
        freopen("cool.in", "r", stdin);
        freopen("cool.out", "w", stdout);
        N = read(), M = read();
        for(reg int i = 1; i <= N; i ++)
                for(reg int j = 1; j <= M; j ++) A[i][j] = read(), B[i][j] = A[i][j];
        for(reg int i = 1; i+1 <= N; i ++)
                for(reg int j = 1; j+1 <= M; j ++) A[i][j] = !chk(i, j);
/* for(reg int i = 1; i <= N; i ++){ for(reg int j = 1; j <= M; j ++) printf("%d ", A[i][j]); printf("\n"); } */

        N --, M --;

        for(reg int j = 1; j <= M; j ++)
                for(reg int i = 1; i <= N; i ++){
                        if(A[i][j] != 0) continue ;
                        Up[i][j] = Up[i-1][j] + 1;
                }
        /* printf("===\n"); for(reg int i = 1; i <= N; i ++){ for(reg int j = 1; j <= M; j ++) printf("%d ", Up[i][j]); printf("\n"); } */
        for(reg int i = 1; i <= N; i ++){
                std::stack <int> stk; 
                std::stack <int> stk_2;
                memset(Rd, 0, sizeof Rd);
                memset(Ld, 0, sizeof Ld);

                for(reg int j = 1; j <= M; j ++){
                        while(!stk.empty() && stk.top() > Up[i][j]) Rd[stk_2.top()] = j, stk.pop(), stk_2.pop();
                        stk.push(Up[i][j]);
                        stk_2.push(j);
                } 
                while(!stk.empty()) Rd[stk_2.top()] = M+1, stk.pop(), stk_2.pop();

                for(reg int j = M; j >= 1; j --){
                        while(!stk.empty() && stk.top() > Up[i][j]) Ld[stk_2.top()] = j, stk.pop(), stk_2.pop();
                        stk.push(Up[i][j]);
                        stk_2.push(j);
                } 
                while(!stk.empty()) Ld[stk_2.top()] = 0, stk.pop(), stk_2.pop();

                /* if(i == N){ printf("***==========\n"); for(reg int j = 1; j <= M; j ++) printf("%d ", Ld[j]); printf("\n"); for(reg int j = 1; j <= M; j ++) printf("%d ", Rd[j]); printf("\n"); } */

                for(reg int j = 1; j <= M; j ++){
        // if(j == 5 && i == 5) printf("%d %d %d %d\n", Up[i][j], Rd[j], Ld[j], Rd[j]-Ld[j]-1);
                        Ans = std::max(Ans, (Up[i][j]+1) * (Rd[j]-Ld[j])); 
                }
        }
        printf("%d\n", Ans);
        return 0;
}