洛谷P2216 [HAOI2007]理想的正方形（RMQ+枚舉）

這道題可以用RMQ來做。

RMQ原本是對一個數列進行預處理，這裡我們隻需要對矩陣的每一行都進行一次預處理就好。然後枚舉可能的所有的正方形，用RMQ查詢這個正方形裡面的最大值和最小值，不斷更新最大值與最小值之差就好。

// luogu-judger-enable-o2
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
const int inf=1e9+5;		//inf記得開的大一點，否則會出錯的
const int maxn=1e3+5;
int map[maxn][maxn];
int dp1[maxn][maxn][10],dp2[maxn][maxn][10];	//dp1記錄最大值，dp2記錄最小值

int min_(int x,int y)		//可以用algorithm頭檔案裡的比較函數，但這裡特意自己寫了一個是防止逾時（STL速度是比較慢的）
{
	return x<y? x:y;
}

int max_(int x,int y)
{
	return x>y? x:y;
}

int main()
{
	int a,b,n;
	scanf("%d%d%d",&a,&b,&n);
	for(int i=1;i<=a;++i)
		for(int j=1;j<=b;++j)
			scanf("%d",&map[i][j]);
	if(n==1)
	{
		printf("0\n");
		return 0;
	}
	for(int i=1;i<=a;++i)	//逐行預處理
	{
		for(int j=1;j<=b;++j)	dp1[i][j][0]=dp2[i][j][0]=map[i][j];
		for(int j=1;(1<<j)<=b;++j)
			for(int k=1;k+(1<<j)-1<=b;++k)
			{
				dp1[i][k][j]=max_(dp1[i][k][j-1],dp1[i][k+(1<<(j-1))][j-1]);
				dp2[i][k][j]=min_(dp2[i][k][j-1],dp2[i][k+(1<<(j-1))][j-1]);
			}
	}
	int ans=inf,k=0;
	while((1<<(k+1))<=n)	++k;
	for(int i=1;i<=a-n+1;++i)	//枚舉正方形的左上頂點來枚舉正方形
		for(int j=1;j<=b-n+1;++j)
		{
			int ma,mi,l,r;
			l=j; r=j+n-(1<<k);	
			ma=max_(dp1[i][l][k],dp1[i][r][k]);
			mi=min_(dp2[i][l][k],dp2[i][r][k]);
			for(int p=i+1;p<=i+n-1;++p)	//掃遍正方形的每一行
			{
				ma=max_(ma,max_(dp1[p][l][k],dp1[p][r][k]));
				mi=min_(mi,min_(dp2[p][l][k],dp2[p][r][k]));
			}
			ans=min_(ans,ma-mi);
		}
	printf("%d\n",ans);
	return 0;
}