首页 > 代码库 > HDU 2888:Check Corners(二维RMQ)
HDU 2888:Check Corners(二维RMQ)
http://acm.hdu.edu.cn/showproblem.php?pid=2888
题意:给出一个n*m的矩阵,还有q个询问,对于每个询问有一对(x1,y1)和(x2,y2),求这个子矩阵中的最大值,和判断四个角有没有等于这个最大值的。
思路:二维RMQ模板题。注意内存卡的挺紧的。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <cmath> 5 using namespace std; 6 #define N 301 7 int dp[N][N][9][9], mp[N][N], n, m, x1, x2, y11, y2; 8 // 内存刚好 30704kB 卡着过了 9 10 void Init() {11 for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) dp[i][j][0][0] = mp[i][j];12 int A = (int)(log(n) / log(2)), B = (int)(log(m) / log(2));13 for(int j = 0; j <= A; j++) {14 for(int y = 0; y <= B; y++) {15 if(j == 0 && y == 0) continue;16 for(int i = 1; i + (1 << j) - 1 <= n; i++)17 for(int x = 1; x + (1 << y) - 1 <= m; x++)18 if(j) dp[i][x][j][y] = max(dp[i][x][j-1][y], dp[i+(1<<(j-1))][x][j-1][y]);19 else dp[i][x][j][y] = max(dp[i][x][j][y-1], dp[i][x+(1<<(y-1))][j][y-1]);20 }21 }22 }23 24 int Query() {25 int A = (int)(log(x2 - x1 + 1) / log(2)), B = (int)(log(y2 - y11 + 1) / log(2));26 int a = dp[x1][y11][A][B];27 int b = dp[x2-(1<<A)+1][y11][A][B];28 int c = dp[x1][y2-(1<<B)+1][A][B];29 int d = dp[x2-(1<<A)+1][y2-(1<<B)+1][A][B];30 return max(a, max(b, max(c, d)));31 }32 33 bool check(int val) {34 if(mp[x1][y11] == val || mp[x2][y2] == val || mp[x1][y2] == val || mp[x2][y11] == val) return true;35 return false;36 }37 38 int main() {39 while(~scanf("%d%d", &n, &m)) {40 for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) scanf("%d", &mp[i][j]);41 int q; scanf("%d", &q);42 Init();43 while(q--) {44 scanf("%d%d%d%d", &x1, &y11, &x2, &y2);45 int val = Query();46 printf("%d ", val);47 if(check(val)) puts("yes");48 else puts("no");49 }50 }51 return 0;52 }
HDU 2888:Check Corners(二维RMQ)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。