二维RMQ hdu 2888

题目:点这里

题意:给出一个n*m的矩阵,然后又Q个询问:每个询问有x1,y1,x2,y2,x1,y1为子矩阵的左上角坐标,x2,y2为右上角的坐标。求此子矩阵中元素最大值,判断最大值是否在子矩阵四个角上,在就输出yes,否则输出no。

分析:二维RMQ直接上代码。

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
const int max_=;
int dp[max_][max_][][];//RMQ的递推数组。1,3维是行,2 4维是列。
int a[max_][max_];
void RMQ_init(int n,int m)
{
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)//初始化
{
dp[i][j][][]=a[i][j];
}
for(int i=;(<<i)<=n;i++)
for(int j=;(<<j)<=m;j++)
if(i||j)//i,j不都为0。
{
for(int ii=;ii+(<<i)-<=n;ii++)
for(int jj=;jj+(<<j)-<=m;jj++)
{
if(i)//对行递推。
{
int k=<<(i-);
dp[ii][jj][i][j]=max(dp[ii][jj][i-][j],dp[ii+k][jj][i-][j]);
}
else
{
int k=<<(j-);
dp[ii][jj][i][j]=max(dp[ii][jj][i][j-],dp[ii][jj+k][i][j-]);
}
}
}
}
int RMQ_Q(int x1,int y1,int x2,int y2)//查询
{
int k1=;
while((<<(k1+))<=x2-x1+)k1++;
int k2=;
while((<<(k2+))<=y2-y1+)k2++;
x2=x2-(<<k1)+;
y2=y2-(<<k2)+;
return max(max(dp[x1][y1][k1][k2],dp[x1][y2][k1][k2]),max(dp[x2][y1][k1][k2],dp[x2][y2][k1][k2]));
}
int main()
{
int n,m;
while(~scanf("%d %d",&n,&m))
{
if(!n&&!m)
break;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
scanf("%d",&a[i][j]);
}
RMQ_init(n,m);
int k;
scanf("%d",&k);
while(k--)
{
int x1,y1,x2,y2;
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
int temp=RMQ_Q(x1,y1,x2,y2);
printf("%d ",temp);
if(temp==a[x1][y1]||temp==a[x1][y2]||temp==a[x2][y1]||temp==a[x2][y2])
printf("yes\n");
else
printf("no\n");
}
}
}
上一篇:Windows 10移动版如何继续使用


下一篇:HDU 2888:Check Corners(二维RMQ)