针对一些二维区间最值问题,用一维RMQ来解决显然是不够的。所以,要改进算法。鉴于网上没有PASCAL版的RMQ标程与解析,所以小可在这里简单的讲一下。

   核心思想和一维的一样,只是在计算区间时略有不同。用数组F[i,j,k]表示以i,j为左上角的矩形,长度为(1 shl k),然后在循环时取四个矩形的最值,具体伪代码如下:

  for k:=1 to x do              // x为要处理矩形的最大边长的trunc(logmax)值
    for i:=1 to n+1-(1 shl k) do
      for j:=1 to m+1-(1 shl k) do      //循环上和一维的一样,只是多加了一层而已 
       f[i,j,k]:=max(f[i,j,k-1],f[i+1 shl (k-1),j,k-1],f[i,j+1 shl (k-1),k-1],f[i+1 shl (k-1),j+1 shl (k-1),k-1]);

           //   分成四块正方形计算

  查询时和一维的一样,这里不再详讲。

  总的时间复杂度为O(logN*N+M)  在这里将待处理矩形看做正方形,M为询问次数

  提别提醒:因为循环次数较多,反复调用shl函数会导致常数变大,所以有时可以开一个数组预存要用到的值,以减少时间上的浪费。

  "理想的正方形"就可以用以上方法完美的解决掉,时间略慢,附上代码

AC代码:

program zht;

var n,m,s,x,i,j,k,q,w,ans:longint;

f1,f2:array[0..1000,0..1000,0..7] of longint;

z:longint;

function mm(a,b:longint):longint;

begin if a>b then mm:=a else mm:=b;

end;

function max(a,b,c,d:longint):longint;

begin

max:=mm(mm(a,b),mm(c,d));

end;

function mmm(a,b:longint):longint;

begin

if a<b then mmm:=a else mmm:=b; end;

function min(a,b,c,d:longint):longint;

begin

min:=mmm(mmm(a,b),mmm(c,d));

end;

begin

assign(input,'square.in');

assign(output,'square.out');

reset(input);

rewrite(output);

readln(n,m,s);

for i:=1 to n do

 for j:=1 to m do

  begin

  read(z);

  f1[i,j,0]:=z;

  f2[i,j,0]:=z;

  end;

x:=trunc(ln(s)/ln(2));

for k:=1 to x do

 for i:=1 to n+1-(1 shl k) do

  for j:=1 to m+1-(1 shl k) do

  begin

  f1[i,j,k]:=max(f1[i,j,k-1],f1[i+1 shl (k-1),j,k-1],f1[i,j+1 shl (k-1),k-1],f1[i+1 shl (k-1),j+1 shl (k-1),k-1]);           f2[i,j,k]:=min(f2[i,j,k-1],f2[i+1 shl (k-1),j,k-1],f2[i,j+1 shl (k-1),k-1],f2[i+1 shl (k-1),j+1 shl (k-1),k-1]);

  end;         // 两个存最值的数组预处理

ans:=maxlongint;

for i:=1 to n-s+1 do

 for j:=1 to m-s+1 do

 begin

 q:=max(f1[i,j,x],f1[i+s-(1 shl x),j,x],f1[i,j+s-(1 shl x),x],f1[i+s-(1 shl x),j+s-(1 shl x),x]);

 w:=min(f2[i,j,x],f2[i+s-(1 shl x),j,x],f2[i,j+s-(1 shl x),x],f2[i+s-(1 shl x),j+s-(1 shl x),x]);

 ans:=mmm(q-w,ans);     // 穷举顶点,计算最小差值

 end;

writeln(ans);

close(input);

close(output);

end.

  <Marvolo原创,严禁转载>

04-28 05:12