[BZOJ1047][HAOI2007]理想的正方形(RMQ+DP)

题意

有一个a*b的整数组成的矩阵，现请你从中找出一个n*n的正方形区域，使得该区域所有数中的最大值和最小值
的差最小。

思路

RMQ求

再DP

代码

#include<cstdio>

#include<cmath>

#define max(a,b) (a>b?a:b)

#define min(a,b) (a<b?a:b)

using namespace std;

#define N 1005

int a,b,n;

int m[N][N];

int ans=0x3fffffff;

int Min[N][N][],Max[N][N][];

void rmq()

{

    for(int i=;i<=a;++i)for(int j=;j<=b;++j)Min[i][j][]=Max[i][j][]=m[i][j];

    for(int k=;k<=;++k)

    for(int i=;i<=a-(<<k)+;++i){

        for(int j=;j<=b-(<<k)+;++j)

        {

            Max[i][j][k]=max(max(Max[i][j][k-],Max[i+(<<k-)][j][k-]),max(Max[i][j+(<<k-)][k-],Max[i+(<<k-)][j+(<<k-)][k-]));

            Min[i][j][k]=min(min(Min[i][j][k-],Min[i+(<<k-)][j][k-]),min(Min[i][j+(<<k-)][k-],Min[i+(<<k-)][j+(<<k-)][k-]));

        }

    }

}

int Qr(int x,int y,int xx,int yy)

{

    int len=log2(xx-x);

    int maxx=max(max(Max[x][y][len],Max[xx-(<<len)+][y][len]),max(Max[x][yy-(<<len)+][len],Max[xx-(<<len)+][yy-(<<len)+][len]));

    int minn=min(min(Min[x][y][len],Min[xx-(<<len)+][y][len]),min(Min[x][yy-(<<len)+][len],Min[xx-(<<len)+][yy-(<<len)+][len]));

    return maxx-minn;

}

int main()

{

    scanf("%d%d%d",&a,&b,&n);

    for(int i=;i<=a;++i)

    for(int j=;j<=b;++j)

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

    rmq();

    for(int i=n;i<=a;++i)

    for(int j=n;j<=b;++j)

    ans=min(ans,Qr(i-n+,j-n+,i,j));

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

    return ;

}