vijos1255——月饼盒 详细题解
发表时间：2010-05-04 20:28:40 浏览(3363) 评论(2)
VJ1255是一道经典的利用悬线法求极大子矩形的问题.首先,最终选择的矩形必须不包含洞,称这样的矩形为可行矩形.最终选择的可行矩形一定不会被包含在任何一个其他的可行矩形之内,否则选择那个矩形一定更好.
在求解之前,先要进行预处理.用sum[i,j]表示(1,1)到(i,j)这个范围的格子中的权值之和.
设(i,j)这个格子的权值为a[i,j],则sum[i,j]:=sum[i-1,j]+sum[i,j-1]-sum[i-1,j-1]+a[i,j].然后如果想求(x1,y1)到(x2,y2)的矩形的权和,就是sum[x2,y2]-sum[x1-1,y2]-sum[x2,y1-1]+sum[x1-1,y1-1].(x1<=x2,y1<=y2)
然后就是问题的核心部分,求极大子矩形.极大子矩形首先是可行矩形,其次不被包含于任何其他可行矩形.算法的思想是对于当前要计算的节点,向上、左、右三个方向拓展，其中优先向上拓展。在做之前要按行预处理一下.得到每个格子向左最多拓展多少个连续的可行格子,向右能拓展多少个.方法是:left[i,j]:={left[i,j-1]+1((i,j)格子不是洞);0((i,j)格子是洞)}右边的同理.然后就从上到下从左到右计算每一个格子.如果该格子是洞,那么跳过.否则如果该格子正上方的格子是洞,跳过.否则,记录up[i,j]:=up[i-1,j]+1,left[i,j]:=min{left[i,j].left[i-1,j]},right[i,j]:=min{right[i,j[,right[i-1,j]}.这么做的结果导致的是算出了每个格子最多能向上拓展到哪个格子,以及在这个情况下这一列空格向左右移动,最多平移到哪个位置而不碰到障碍(洞).最后,对于格子(i,j),需要计算一个矩形的权值.x1=i-up[i,j]+1.y1=j-left[i,j]+1,x2=i,y2=j+right[i,j]-1.然后其中的最大值就是答案.
参考程序:
program candy;
var i,j,k,r,c,ans:longint;
left,right:array[0..1001,1..2] of longint;
shang:array[0..1001,1..2] of longint;
data:array[0..1001,1..1000] of longint;
sum:array[0..1000,0..1000] of longint;
function ms(x,y:longint):longint;
begin
if x>y then exit(y) else exit(x);
end;
function mx(x,y:longint):longint;
begin
if x<y then exit(y) else exit(x);
end;
begin
read(r,c);
for i:=1 to r do
for j:=1 to c do
read(data[i,j]);
for i:=1 to r do
for j:=1 to c do
sum[i,j]:=sum[i,j-1]+sum[i-1,j]-sum[i-1,j-1]+data[i,j];
for i:=1 to c do
begin
left[i,2]:=10000;right[i,2]:=10000;
end;
for i:=1 to r do
begin
if i mod 2=1 then
begin
for j:=1 to c do
if data[i,j]>0 then
begin
left[j,1]:=left[j-1,1]+1;
shang[j,1]:=shang[j,2]+1;
end else
begin
left[j,1]:=0;
shang[j,1]:=0;
end;
for j:=c downto 1 do
if data[i,j]>0 then
right[j,1]:=right[j+1,1]+1 else right[j,1]:=0;
for j:=1 to c do
begin
if shang[j,1]>1 then begin
left[j,1]:=ms(left[j,1],left[j,2]);
right[j,1]:=ms(right[j,1],right[j,2]);
end;
k:=sum[i,j+right[j,1]-1] -sum[i,j-left[j,1]]-sum[i-shang[j,1],j+right[j,1]-1]+sum[i-shang[j,1],j-left[j,1]];
if k>ans then ans:=k;
end;
end else
begin
for j:=1 to c do
if data[i,j]>0 then
begin
left[j,2]:=left[j-1,2]+1;
shang[j,2]:=shang[j,1]+1;
end else
begin
left[j,2]:=0;
shang[j,2]:=0;
end;
for j:=c downto 1 do
if data[i,j]>0 then
right[j,2]:=right[j+1,2]+1 else right[j,2]:=0;
for j:=1 to c do
begin
if shang[j,2]>1 then begin
left[j,2]:=ms(left[j,1],left[j,2]);
right[j,2]:=ms(right[j,1],right[j,2]);
end;
k:=sum[i,j+right[j,2]-1]-sum[i,j-left[j,2]]-sum[i-shang[j,2],j+right[j,2]-1]+sum[i-shang[j,2],j-left[j,2]];
if k>ans then ans:=k;
end;
end;
end;
writeln(ans);
end.
在求解之前,先要进行预处理.用sum[i,j]表示(1,1)到(i,j)这个范围的格子中的权值之和.
设(i,j)这个格子的权值为a[i,j],则sum[i,j]:=sum[i-1,j]+sum[i,j-1]-sum[i-1,j-1]+a[i,j].然后如果想求(x1,y1)到(x2,y2)的矩形的权和,就是sum[x2,y2]-sum[x1-1,y2]-sum[x2,y1-1]+sum[x1-1,y1-1].(x1<=x2,y1<=y2)
然后就是问题的核心部分,求极大子矩形.极大子矩形首先是可行矩形,其次不被包含于任何其他可行矩形.算法的思想是对于当前要计算的节点,向上、左、右三个方向拓展，其中优先向上拓展。在做之前要按行预处理一下.得到每个格子向左最多拓展多少个连续的可行格子,向右能拓展多少个.方法是:left[i,j]:={left[i,j-1]+1((i,j)格子不是洞);0((i,j)格子是洞)}右边的同理.然后就从上到下从左到右计算每一个格子.如果该格子是洞,那么跳过.否则如果该格子正上方的格子是洞,跳过.否则,记录up[i,j]:=up[i-1,j]+1,left[i,j]:=min{left[i,j].left[i-1,j]},right[i,j]:=min{right[i,j[,right[i-1,j]}.这么做的结果导致的是算出了每个格子最多能向上拓展到哪个格子,以及在这个情况下这一列空格向左右移动,最多平移到哪个位置而不碰到障碍(洞).最后,对于格子(i,j),需要计算一个矩形的权值.x1=i-up[i,j]+1.y1=j-left[i,j]+1,x2=i,y2=j+right[i,j]-1.然后其中的最大值就是答案.
参考程序:
program candy;
var i,j,k,r,c,ans:longint;
left,right:array[0..1001,1..2] of longint;
shang:array[0..1001,1..2] of longint;
data:array[0..1001,1..1000] of longint;
sum:array[0..1000,0..1000] of longint;
function ms(x,y:longint):longint;
begin
if x>y then exit(y) else exit(x);
end;
function mx(x,y:longint):longint;
begin
if x<y then exit(y) else exit(x);
end;
begin
read(r,c);
for i:=1 to r do
for j:=1 to c do
read(data[i,j]);
for i:=1 to r do
for j:=1 to c do
sum[i,j]:=sum[i,j-1]+sum[i-1,j]-sum[i-1,j-1]+data[i,j];
for i:=1 to c do
begin
left[i,2]:=10000;right[i,2]:=10000;
end;
for i:=1 to r do
begin
if i mod 2=1 then
begin
for j:=1 to c do
if data[i,j]>0 then
begin
left[j,1]:=left[j-1,1]+1;
shang[j,1]:=shang[j,2]+1;
end else
begin
left[j,1]:=0;
shang[j,1]:=0;
end;
for j:=c downto 1 do
if data[i,j]>0 then
right[j,1]:=right[j+1,1]+1 else right[j,1]:=0;
for j:=1 to c do
begin
if shang[j,1]>1 then begin
left[j,1]:=ms(left[j,1],left[j,2]);
right[j,1]:=ms(right[j,1],right[j,2]);
end;
k:=sum[i,j+right[j,1]-1] -sum[i,j-left[j,1]]-sum[i-shang[j,1],j+right[j,1]-1]+sum[i-shang[j,1],j-left[j,1]];
if k>ans then ans:=k;
end;
end else
begin
for j:=1 to c do
if data[i,j]>0 then
begin
left[j,2]:=left[j-1,2]+1;
shang[j,2]:=shang[j,1]+1;
end else
begin
left[j,2]:=0;
shang[j,2]:=0;
end;
for j:=c downto 1 do
if data[i,j]>0 then
right[j,2]:=right[j+1,2]+1 else right[j,2]:=0;
for j:=1 to c do
begin
if shang[j,2]>1 then begin
left[j,2]:=ms(left[j,1],left[j,2]);
right[j,2]:=ms(right[j,1],right[j,2]);
end;
k:=sum[i,j+right[j,2]-1]-sum[i,j-left[j,2]]-sum[i-shang[j,2],j+right[j,2]-1]+sum[i-shang[j,2],j-left[j,2]];
if k>ans then ans:=k;
end;
end;
end;
writeln(ans);
end.
网友评论：
 | 1 Guest 于 2010-05-10 19:24:22 说： | 回复 |
|---|---|---|
嗯，不错
| ||
| 2 Guest 于 2010-06-14 02:58:34 说： | 回复 |
呵呵，还好吧，怎么没有注释啊。。。 |