本文主要是介绍POJ 2019 Cornfields 二维RMQ，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目来源：POJ 2019 Cornfields
题意：求正方形二维区间最大最小值的差
思路：直接二维ST搞 试模版而已
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 255;
int dp[maxn][maxn][8][8];
int dp2[maxn][maxn][8][8];
int a[maxn][maxn];
int n, m;
void RMQ_init(int n)
{for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++){dp[i][j][0][0] = a[i][j];dp2[i][j][0][0] = a[i][j];}int k = (int) (log((double)n + 0.2) / log(2.0));for(int x = 0; x <= k; x++)for(int y = 0; y <= k; y++){if(!x && !y)continue;for(int i = 0; i + (1<<x) - 1 <= n; i++)for(int j = 0; j + (1<<y) - 1 <= n; j++){if(x == 0){dp[i][j][x][y] = max(dp[i][j][x][y-1], dp[i][j+(1<<(y-1))][x][y-1]);dp2[i][j][x][y] = min(dp2[i][j][x][y-1], dp2[i][j+(1<<(y-1))][x][y-1]);}else{dp[i][j][x][y] = max(dp[i][j][x-1][y], dp[i+(1<<(x-1))][j][x-1][y]);dp2[i][j][x][y] = min(dp2[i][j][x-1][y], dp2[i+(1<<(x-1))][j][x-1][y]);}}}
}
int RMQ(int x1, int y1, int x2, int y2)
{int kx = log(double(x2 - x1 + 1)) / log(2.0);int ky = log(double(y2 - y1 + 1)) / log(2.0);int ans1 = 0;ans1 = max(ans1, dp[x1][y1][kx][ky]);ans1 = max(ans1, dp[x2-(1<<kx)+1][y1][kx][ky]);ans1 = max(ans1, dp[x1][y2-(1<<ky)+1][kx][ky]);ans1 = max(ans1, dp[x2-(1<<kx)+1][y2-(1<<ky)+1][kx][ky]);int ans2 = 999999999;ans2 = min(ans2, dp2[x1][y1][kx][ky]);ans2 = min(ans2, dp2[x2-(1<<kx)+1][y1][kx][ky]);ans2 = min(ans2, dp2[x1][y2-(1<<ky)+1][kx][ky]);ans2 = min(ans2, dp2[x2-(1<<kx)+1][y2-(1<<ky)+1][kx][ky]);return ans1 - ans2;
}int main()
{int q;scanf("%d %d %d", &n, &m, &q);for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)scanf("%d", &a[i][j]);RMQ_init(n);//printf("Case %d:\n", cas++);while(q--){int l, r;scanf("%d %d", &l, &r);int ll = l + m - 1;int rr = r + m - 1;if(ll > n)ll = n;if(rr > n)rr = n;printf("%d\n", RMQ(l, r, ll, rr));}return 0;
}这篇关于POJ 2019 Cornfields 二维RMQ的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
