牛客 - 700I - Matrix Again - 二维RMQ

https://ac.nowcoder.com/acm/contest/700/I

二维RMQ，贴个板子，注意爆内存，用char就可以了，char也可以存负数。

然后二分枚举对角线长度，理由很简单。

矩阵变大，极值只会变大不会变小。满足单调性。
#include<bits/stdc++.h>

using namespace std;

#define MAXN 501

int n,m,g;

int rec[MAXN][MAXN];

char dp[MAXN][MAXN][11][11];

char dp1[MAXN][MAXN][11][11];

inline int maxm(int a,int b,int c,int d) {

    if(a<b)

        a=b;

    if(a<c)

        a=c;

    if(a<d)

        a=d;

    return a;

}

inline int minm(int a,int b,int c,int d) {

    if(b<a)

        a=b;

    if(c<a)

        a=c;

    if(d<a)

        a=d;

    return a;

}

void st() {

    for(int k=0; (1<<k)<=n; k++)

        for(int l=0; (1<<l)<=m; l++)

            for(int i=1; i+(1<<k)-1<=n; i++)

                for(int j=1; j+(1<<l)-1<=m; j++) {

                    if(!k&&!l) {

                        dp1[i][j][k][l]=dp[i][j][k][l]=rec[i][j];

                    } else if(k==0) {

                        dp[i][j][k][l]=max(dp[i][j][k][l-1],dp[i][j+(1<<(l-1))][k][l-1]);

                        dp1[i][j][k][l]=min(dp1[i][j][k][l-1],dp1[i][j+(1<<(l-1))][k][l-1]);

                    } else if(l==0) {

                        dp[i][j][k][l]=max(dp[i][j][k-1][l],dp[i+(1<<(k-1))][j][k-1][l]);

                        dp1[i][j][k][l]=min(dp1[i][j][k-1][l],dp1[i+(1<<(k-1))][j][k-1][l]);

                    } else {

                        dp[i][j][k][l]=maxm(dp[i][j][k-1][l-1],dp[i+(1<<(k-1))][j][k-1][l-1],

                                            dp[i][j+(1<<(l-1))][k-1][l-1],dp[i+(1<<(k-1))][j+(1<<(l-1))][k-1][l-1]);

                        dp1[i][j][k][l]=minm(dp1[i][j][k-1][l-1],dp1[i+(1<<(k-1))][j][k-1][l-1],

                                             dp1[i][j+(1<<(l-1))][k-1][l-1],dp1[i+(1<<(k-1))][j+(1<<(l-1))][k-1][l-1]);

                    }

                    //printf("dp[%d][%d][%d][%d]=%d\n",i,j,k,l,dp[i][j][k][l]);

                }

}

int rmq2dmax(int x,int y,int x1,int y1) {

    int k=0;

    while((x1-x+1)>=(1<<k))

        k++;

    k--;

    int l=0;

    while((y1-y+1)>=(1<<l))

        l++;

    l--;

    return maxm(dp[x][y][k][l],dp[x1-(1<<k)+1][y][k][l],

                dp[x][y1-(1<<l)+1][k][l],dp[x1-(1<<k)+1][y1-(1<<l)+1][k][l]);

}

int rmq2dmin(int x,int y,int x1,int y1) {

    int k=0;

    while((x1-x+1)>=(1<<k))

        k++;

    k--;

    int l=0;

    while((y1-y+1)>=(1<<l))

        l++;

    l--;

    return minm(dp1[x][y][k][l],dp1[x1-(1<<k)+1][y][k][l],

                dp1[x][y1-(1<<l)+1][k][l],dp1[x1-(1<<k)+1][y1-(1<<l)+1][k][l]);

}

bool check(int len,int &suc) {

    for(int i=1; i<=n; i++) {

        if(i+len-1>n)

            break;

        for(int j=1; j<=m; j++) {

            if(j+len-1>m)

                break;

            int t=rmq2dmax(i,j,i+len-1,j+len-1)-rmq2dmin(i,j,i+len-1,j+len-1);

            if(t<=g) {

                suc=1;

                return 1;

            }

        }

    }

    return 0;

}

int main() {

    scanf("%d%d%d",&n,&m,&g);

    for(int i=1; i<=n; i++) {

        for(int j=1; j<=m; j++) {

            scanf("%d",&rec[i][j]);

        }

    }

    st();

    int l=1,r=min(n,m);

    int ans=-1;

    while(1) {

        int len=(l+r)>>1;

        int suc=0;

        if(l==len){

            check(r,suc);

            if(suc){

                ans=r;

            }

            else{

                ans=l;

            }

            break;

        }

        check(len,suc);

        if(suc) {

            l=len;

        } else {

            r=len-1;

        }

    }

    printf("%d\n",ans);

}
巴特西

牛客 - 700I - Matrix Again - 二维RMQ - 二分

最新文章

热门文章
