【BZOJ1047】[HAOI2007]理想的正方形

题面

bzoj

洛谷

题解

二维\(st\)表，代码是以前的

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<string>

#include<cmath>

#include<vector>

#include<queue>

#include<map>

#include<set>

#include<algorithm>

#include<ctime>

#define RG register

#define file(x) freopen(x".in","r",stdin);

using namespace std;

#define ll long long

inline int gi(){

    int data=0,w=1;

    char ch=0;

    while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();

    if(ch=='-') w=-1,ch=getchar();

    while(ch>='0'&&ch<='9') data=data*10+ch-'0',ch=getchar();

    return w*data;

}

#define N 1010

int a,b,n;

int val[N][N],dp1[N][N][11],dp2[N][N][11],lg[N];

int MX(int e,int f,int g,int h){

	return max(max(e,f),max(g,h));

}

int MI(int e,int f,int g,int h){

	return min(min(e,f),min(g,h));

}

void Pre(){

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

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

	    dp1[i][j][0]=dp2[i][j][0]=val[i][j];

	for(RG int k=1;k<=10;k++)

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

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

	    dp1[i][j][k]=MX (dp1[i][j][k-1],

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

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

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

		dp2[i][j][k]=MI (dp2[i][j][k-1],

	                     dp2[i+(1<<k-1)][j][k-1],

						 dp2[i][j+(1<<k-1)][k-1],

						 dp2[i+(1<<k-1)][j+(1<<k-1)][k-1]);

	}

}

int query(int i,int j,int dis){

	int t=log(n)/log(2);

	int sum;

	sum=(MX(dp1[i][j][t],dp1[n+i-(1<<t)][j][t],dp1[i][j+n-(1<<t)][t],dp1[i+n-(1<<t)][j+n-(1<<t)][t])-

	     MI(dp2[i][j][t],dp2[i+n-(1<<t)][j][t],dp2[i][j+n-(1<<t)][t],dp2[i+n-(1<<t)][j+n-(1<<t)][t]));

	return sum;

}

int main(){

	a=gi();b=gi();n=gi();

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

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

	    val[i][j]=gi();

	Pre();

	int MIN=0x7fffffff;;

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

	   for(RG int j=1;j<=b-n+1;j++)

	       MIN=min(MIN,query(i,j,n));

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

	return 0;

}