https://www.luogu.org/problemnew/show/P2216#sub
有一个a*b的整数组成的矩阵，现请你从中找出一个n*n的正方形区域，使得该区域所有数中的最大值和最小值的差最小。
in:
5 4 2
1 2 5 6
0 17 16 0
16 17 2 1
2 10 2 1
1 2 2 2
out:
1
从a * b的矩阵里选出一个n * n的矩阵，使矩阵内最大值和最小值差值最小。
我们可以想到分别求出矩阵的最小值和最大值求解
我们用dp[k][i][j][2]表示以i, j为左上角大小为k * k的矩阵的最大最小值
对于左上角(i, j)的矩阵，他的最值即是dp[k][i][j][0/1] = min/max(dp[k - 1][i][j][0/1], min(dp[k - 1][i][j + 1][0/1], min(dp[k - 1][i + 1][j][0/1], dp[k - 1][i + 1][j + 1][0/1])));
但程序空间使用太大，直接优化掉第一维，可以循环直接求解
而时间复杂度也不优秀，在O2优化后可以过，应该要用单调队列优化
#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 1000 + 5;inline void read(int &x){ int data = 0, w = 1; char ch = getchar(); while(ch != '-' && !isdigit(ch)) ch = getchar(); if(ch == '-') w = -1, ch = getchar(); while(isdigit(ch)) data = 10 * data + ch - '0', ch = getchar(); x = data * w;}void write(int x){ if(x < 0) putchar('-'), x = -x; if(x > 9) write(x / 10); putchar('0' + x % 10);}int x[maxn][maxn];int dp[maxn][maxn][2]; //max - minint main(){ int a, b, n; read(a), read(b), read(n); for(int i = 1; i <= a; i++) for(int j = 1; j <= b; j++) { read(x[i][j]); dp[i][j][0] = dp[i][j][1] = x[i][j]; } for(int k = 2; k <= n; k++) { for(int i = 1; i <= a; i++) { for(int j = 1; j <= b; j++) { if(k + i - 1 > a || j + k - 1 > b) continue; dp[i][j][0] = min(dp[i][j][0], min(dp[i][j + 1][0], min(dp[i + 1][j][0], dp[i + 1][j + 1][0]))); dp[i][j][1] = max(dp[i][j][1], max(dp[i][j + 1][1], max(dp[i + 1][j][1], dp[i + 1][j + 1][1]))); } } } int ans = 0x3f3f3f3f; for(int i = 1; i <= a; i++) { for(int j = 1; j <= b; j++) { if(i + n - 1 > a || j + n - 1 > b) continue; ans = min(ans, dp[i][j][1] - dp[i][j][0]); } } write(ans); return 0;}
优化可以用st表或者单调队列
正如上面所说，每个矩阵的值由它本身、右矩阵、下矩阵、右下矩阵的上一状态的值决定，发现和st表的原理很像，可以写成二维的st表
st[i][j][2]表示由(i,j)为左上角，大小为k * k的矩阵的最大值和最小值，节省空间直接优化掉第一维k
所以每个状态转移为st[i][j][0/1] = min/max(st[i][j][0/1], st[i+(1<<k)][j][0/1], st[i][j+(1<<k)][0/1], st[i+(1<<k)][j+(1<<k)][0/1]);
#include<bits/stdc++.h>using namespace std;const int maxn = 1e3 + 100;int arr[maxn][maxn], len, n;int st[maxn][maxn][2];int query(int i, int j) { int _max, _min; _max = max(st[i][j][1], max(st[i + n - (1 << len)][j][1], max(st[i][j + n - (1 << len)][1], st[i + n - (1 << len)][j + n - (1 << len)][1]))); _min = min(st[i][j][0], min(st[i + n - (1 << len)][j][0], min(st[i][j + n - (1 << len)][0], st[i + n - (1 << len)][j + n - (1 << len)][0]))); return _max - _min;}int main(){ int a, b; cin >> a >> b >> n; for(int i = 1; i <= a; i++) for(int j = 1; j <= b; j++) cin >> arr[i][j], st[i][j][0] = st[i][j][1] = arr[i][j]; //预处理st表 len = 0; while((1 << (len + 1)) <= n) len++; for(int k = 0; k < len; k++) { for(int i = 1; i + (1 << k) <= a; i++) { for(int j = 1; j + (1 << k) <= b; j++) { st[i][j][0] = min(st[i][j][0], min(st[i + (1 << k)][j][0], min(st[i][j + (1 << k)][0], st[i + (1 << k)][j + (1 << k)][0]))); st[i][j][1] = max(st[i][j][1], max(st[i + (1 << k)][j][1], max(st[i][j + (1 << k)][1], st[i + (1 << k)][j + (1 << k)][1]))); } } } 维护由i,j为左上角的大小为n的矩阵值 int ans = 0x3f3f3f3f; for(int i = 1; i <= a - n + 1; i++) { for(int j = 1; j <= b - n + 1; j++) { ans = min(ans, query(i, j)); } } cout << ans << endl;}