本文共 2304 字，大约阅读时间需要 7 分钟。
// =====================================================================================// // Filename: zoj2859.cpp// // Description: 2D RMQ -- Orz...卡了输出...// // Version: 1.0// Created: 2012年03月02日 22时17分57秒// Revision: none// Compiler: g++// // Author: SphinX (Whisper), sphinx2010@yahoo.cn// Company: HFUT// // =====================================================================================#include#include #include using namespace std;const int MAXN = 302;const int MAXK = 9;int test, n, m;int mtx[MAXN][MAXN], dp[MAXN][MAXN][MAXK][MAXK];int pow_hash[MAXK], log_hash[MAXN];void preproces(){ log_hash[0] = 0; log_hash[1] = 0; for (int ind = 2, k = 1; ind < MAXN; ++ind) { if ((1 << (k + 1)) <= ind) { ++k; } log_hash[ind] = k; } for (int k = 0; (1 << k) < MAXN; ++k) { pow_hash[k] = (1 << k); } return ;}void initRMQ(){ int k = log_hash[n]; for (int row = 0; row < n; ++row) { for (int col = 0; col < n; ++col) { dp[row][col][0][0] = mtx[row][col]; } } for (int i = 0; i <= k; ++i) { for (int j = 0; j <= k; ++j) { if (0 == i && 0 == j) { continue ; } for (int row = 0; row + pow_hash[i] <= n; ++row) { for (int col = 0; col + pow_hash[j] <= n; ++col) { if (0 == i) { dp[row][col][i][j] = min(dp[row][col][i][j - 1], dp[row][col + pow_hash[j - 1]][i][j - 1]); } else { dp[row][col][i][j] = min(dp[row][col][i - 1][j], dp[row + pow_hash[i - 1]][col][i - 1][j]); } } } } } return ;}int queryRMQ(int r1, int c1, int r2, int c2){ int kr = log_hash[r2 - r1 + 1]; int kc = log_hash[c2 - c1 + 1]; return min( min(dp[r1][c1][kr][kc], dp[r2 - pow_hash[kr] + 1][c2 - pow_hash[kc] + 1][kr][kc]), min(dp[r2 - pow_hash[kr] + 1][c1][kr][kc], dp[r1][c2 - pow_hash[kc] + 1][kr][kc]) );}void ace(){ int cas = 1; int r1, c1, r2, c2; preproces(); for (scanf("%d", &test); test--; ++cas) { scanf("%d", &n); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { scanf("%d", &mtx[i][j]); } } initRMQ(); scanf("%d", &m); while (m--) { scanf("%d %d %d %d", &r1, &c1, &r2, &c2); printf("%d\n", queryRMQ(r1 - 1, c1 - 1, r2 - 1, c2 - 1)); } } return ;}int main(int argc, char *argv[]){ ace(); return EXIT_SUCCESS;}
转载地址：http://ksbqb.baihongyu.com/