题意

有一个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][15],Max[N][N][15]; void rmq() { for(int i=1;i<=a;++i)for(int j=1;j<=b;++j)Min[i][j][0]=Max[i][j][0]=m[i][j]; for(int k=1;k<=10;++k) for(int i=1;i<=a-(1<<k)+1;++i){ for(int j=1;j<=b-(1<<k)+1;++j) { Max[i][j][k]=max(max(Max[i][j][k-1],Max[i+(1<<k-1)][j][k-1]),max(Max[i][j+(1<<k-1)][k-1],Max[i+(1<<k-1)][j+(1<<k-1)][k-1])); Min[i][j][k]=min(min(Min[i][j][k-1],Min[i+(1<<k-1)][j][k-1]),min(Min[i][j+(1<<k-1)][k-1],Min[i+(1<<k-1)][j+(1<<k-1)][k-1])); } } } 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-(1<<len)+1][y][len]),max(Max[x][yy-(1<<len)+1][len],Max[xx-(1<<len)+1][yy-(1<<len)+1][len])); int minn=min(min(Min[x][y][len],Min[xx-(1<<len)+1][y][len]),min(Min[x][yy-(1<<len)+1][len],Min[xx-(1<<len)+1][yy-(1<<len)+1][len])); return maxx-minn; } int main() { scanf("%d%d%d",&a,&b,&n); for(int i=1;i<=a;++i) for(int j=1;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+1,j-n+1,i,j)); printf("%d\n",ans); return 0; }

 

转载于:https://www.cnblogs.com/lincold/p/10293131.html