UC知道求此题解决思路（PASCAL）
来源：百度知道 编辑：UC知道 时间：2024/05/03 00:27:24
【题目描述】
给你一个N*M（N,M<=1000）的01矩形，求一个面积最大的不包含数字1的矩形。
【输入数据】
第一行两个数N，M。
接下来N行，每行M个数为0或1。
【输出数据】
一个数ans表示最大空矩形的面积。
Sample
Easy.in
2 4
1 0 0 0
0 1 1 0
Easy.out
3
给你一个N*M（N,M<=1000）的01矩形，求一个面积最大的不包含数字1的矩形。
【输入数据】
第一行两个数N，M。
接下来N行，每行M个数为0或1。
【输出数据】
一个数ans表示最大空矩形的面积。
Sample
Easy.in
2 4
1 0 0 0
0 1 1 0
Easy.out
3
动态规划
h[i,j]表示弟i行弟j列向上延伸到的高度
l[i,j]表示满足向上延伸到最高左边延伸到的长度,同样r[i,j]表示右边.
时间复杂度O(nm)
http://zhidao.baidu.com/question/119050609.html
我已经回答过了。。。
请问是vijos上的盖房子吗？如果是，那么，现在上不去，上去后，我把我程序发给你！
我现在上去了，程序如下：
var n,m,i,j,max:longint;a:packed array[1..1000,1..1000] of longint;
f:packed array[0..1000,0..1000] of longint;
function min(x,y,z:longint):longint;
begin
min:=x;if y<min then min:=y;if z<min then min:=z;
end;
begin
readln(n,m);max:=-maxlongint;fillchar(f,sizeof(f),0);
for i:=1 to n do
for j:=1 to m do read(a[i,j]);
for i:=1 to n do
for j:=1 to m do begin
if a[i,j]=1 then f[i,j]:=min(f[i-1,j],f[i,j-1],f[i-1,j-1])+1;
if f[i,j]>max then max:=f[i,j];end;
writeln(max);
end.