poj2019 二维RMQ裸题
Time Limit: 1000MS | Memory Limit: 30000K | |
Total Submissions:8623 | Accepted: 4100 |
Description
FJ has, at great expense, surveyed his square farm of N x N hectares (1 <= N <= 250). Each hectare has an integer elevation (0 <= elevation <= 250) associated with it.
FJ will present your program with the elevations and a set of K (1 <= K <= 100,000) queries of the form "in this B x B submatrix, what is the maximum and minimum elevation?". The integer B (1 <= B <= N) is the size of one edge of the square cornfield and is a constant for every inquiry. Help FJ find the best place to put his cornfield.
Input
* Lines 2..N+1: Each line contains N space-separated integers. Line 2 represents row 1; line 3 represents row 2, etc. The first integer on each line represents column 1; the second integer represents column 2; etc.
* Lines N+2..N+K+1: Each line contains two space-separated integers representing a query. The first integer is the top row of the query; the second integer is the left column of the query. The integers are in the range 1..N-B+1.
Output
Sample Input
5 3 1
5 1 2 6 3
1 3 5 2 7
7 2 4 6 1
9 9 8 6 5
0 6 9 3 9
1 2
Sample Output
5 C++代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <math.h>
#include <algorithm>
using namespace std;
#define MAXN 250 + 5
int dp[MAXN][MAXN][];
int dp1[MAXN][MAXN][];
int a[MAXN][MAXN];
int n,m;
void st(){
for(int i=;i<=n;i++)
for(int k=;(<<k)<=m;k++){
for(int j=;j+(<<k)-<=m;j++){
if(k==){
dp[i][j][k]=dp1[i][j][k]=a[i][j];
}
else {
dp[i][j][k]=max(dp[i][j][k-],dp[i][j+(<<(k-))][k-]);
dp1[i][j][k]=min(dp1[i][j][k-],dp1[i][j+(<<(k-))][k-]);
}
}
}
}
int rmq2dmax(int x,int y,int x1,int y1){
int k=log2(y1-y+);
int mm=max(dp[x][y][k],dp[x][y1-(<<k)+][k]);
for(int i=x+;i<=x1;i++)
mm=max(mm,max(dp[i][y][k],dp[i][y1-(<<k)+][k]));
return mm;
}
int rmq2dmin(int x,int y,int x1,int y1){
int k=log2(y1-y+);
int mm=min(dp1[x][y][k],dp1[x][y1-(<<k)+][k]);
for(int i=x+;i<=x1;i++)
mm=min(mm,min(dp1[i][y][k],dp1[i][y1-(<<k)+][k]));
return mm;
} int main(int argc, char const *argv[])
{
int b,k;
scanf("%d%d%d",&n,&b,&k);
m = n;
for(int i = ;i <= n; i++){
for(int j = ;j <= n ; j++){
scanf("%d",&a[i][j]);
}
}
st();
while(k--){
int p,q;
scanf("%d%d",&p,&q);
cout << rmq2dmax(p,q,p + b - ,q + b - ) - rmq2dmin(p,q,p + b - ,q + b - )<< endl;
}
return ;
}
二维RMQ
最新文章
- AnguarJS 第二天----数据绑定
- React Native知识7-TabBarIOS组件
- Mysql 命令大全
- LoadRunner执行过程报错“Failed to connect to server ";xxx.xxx.xxx.xxx:xx";:[10060] connetion time out”
- Rank List
- 用ActionSupport实现验证
- L010-oldboy-mysql-dba-lesson10
- ORA-01078:failure in processing system parameters
- 【HDOJ】1243 反恐训练营
- Outlook2007、2010和Foxmail的簽名設計
- LeetCode-Maximum Subarray[dp]
- Oracle数据库中直方图对执行计划的影响
- c++文件的读写
- 最全spring boot视频系列,你值得拥有
- DB2 sql报错后查证原因与解决问题的方法
- 数字签名、数字证书的原理以及证书的获得java版
- PHP利用CURL_MULTI实现多线程
- 51nod 1421 最大MOD值 | 暴力
- nomad 集群搭建
- .NET Core中NETSDK1061错误解决(转载)