最大矩形pascal

问题描述：

一个N*M的矩阵，每个格子里面有个整数（ 绝对值不大与10 ） ，每个子矩阵（ 至少包含一个元素 ）的价值就是它所包含的格子内的数的和。 现在求两个不相交的子矩阵(不包含相同的格子)，使得他们的价值的乘积最大。

例如： N=3 ， M=4，矩阵如图所示：

2	3	4	5
1	3	2	4
4	3	2	1

最大子矩阵值乘积为288。（左边两列的和为16，右边两列的和为18，结果为16*18=288）。

输入格式：

第一行有两个数字n, m ( n, m < 100)。以后的n行，每行有m个整数。

输出格式：

输出文件只有一个数，即两不相交子矩阵价值乘积的最大值。

样例1：

MATRIX.IN	MATRIX.OUT
1 7 -9 -9 8 8 1 7 -4	128

样例2：

MATRIX.IN	MATRIX.OUT
3 4 2 3 4 5 1 3 2 4 4 3 2 1	288

begin
readln(n,k);
for i:=1 to n do
begin
　　for j:=1 to n do
　　begin
　　 read(a[i,j]);
　　 f[i,j]:=f[i,j-1]+f[i-1,j]-f[i-1,j-1]+a[i,j];
　　end;
end;
for i:=1 to n-k+1 do
　　for j:=1 to n-k+1 do
　　g[i,j]:=f[i+k-1,j+k-1]-f[i+k-1,j-1]-f[i-1,j+k-1]+f[i-1,j-1];
for i:=1 to n-k+1 do
begin
　　l[i+k-1]:=l[i+k-2];
　　for j:=1 to n-k+1 do
　　if g[i,j]>l[i+k-1] then l[i+k-1]:=g[i,j];
end;
for i:=n-k+1 downto 1 do
begin
　　r[i]:=r[i+1];
　　for j:=1 to n-k+1 do
　　if g[i,j]>r[i] then r[i]:=g[i,j];
end;
for i:=1 to n-k+1 do
begin
　　u[i+k-1]:=u[i+k-2];
　　for j:=1 to n-k+1 do
　　if g[j,i]>u[i+k-1] then u[i+k-1]:=g[j,i];
end;
for i:=n-k+1 downto 1 do
begin
　　d[i]:=d[i+1];
　　for j:=1 to n-k+1 do
　　if g[j,i]>d[i] then d[i]:=g[j,i];
end;
ans:=0;
for i:=1 to n-k do
if l[i]+r[i+1]>ans then ans:=l[i]+r[i+1];
for i:=1 to n-k do
if u[i]+d[i+1]>ans then ans:=u[i]+d[i+1];
writeln(ans);
end.

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息