主题：奶牛浴场的问题~~有答就加分哦
fly100
[专家分：50] 发布于 2007-08-25 20:15:00
John的牛场和规划的浴场都是矩形。浴场要完全位于牛场之内，并且浴场的轮廓要与牛场的轮廓平行或者重合。浴场不能覆盖任何产奶点，但是产奶点可以位于浴场的轮廓上。
他当然希望浴场的面积尽可能大了，所以你的任务就是帮她计算浴场的最大面积。
INPUT
输入文件的第一行包含两个整数L和W，分别表示牛场的长和宽。文件的第二行包含一个整数n，表示产奶点的数量。以下n行每行包含两个整数x和y，表示一个产奶点的坐标。所有产奶点都位于牛场内，即：0<=x<=L，0<=y<=W。
OUTPUT
输出文件仅一行，包含一个整数S，表示浴场的最大面积。
Sample Input
10 10
4
1 1
9 1
1 9
9 9
Sample Output
80
Hint
0<=n<=5000
1<=L,W<=30000
最后更新于：2007-08-28 23:23:00
回复列表 （共13个回复）
沙发
Matodied [专家分：7560] 发布于 2007-08-26 11:00:00
TYPE arr = ARRAY[1..32, 1..32] OF BOOLEAN;
VAR
bl, bw, x, y, i, j, l, w, k, s1, s2, max: INTEGER; f: BOOLEAN; a: arr;
BEGIN
READLN(l, w);
READLN(k);
max := 1;
FOR i:=1 TO l DO BEGIN
FOR j:=1 TO w DO a[i, j] := TRUE;
END;
FOR i:=1 TO k DO BEGIN
READLN(s1, s2); a[s1, s2] := FALSE;
END;
FOR bl:=1 TO l DO BEGIN
FOR bw:=1 TO w DO BEGIN
FOR x:=0 TO l - bl DO BEGIN
FOR y:=0 TO w - bw DO BEGIN
f := TRUE;
FOR i:=x + 1 TO x + bl - 1 DO BEGIN
FOR j:=y + 1 TO y + bw - 1 DO BEGIN
IF NOT(a[i, j]) THEN BEGIN
f := FALSE;
END;
END;
END;
IF f THEN BEGIN
IF max < bl * bw THEN max := bl * bw;
END;
END;
END;
END;
END;
WRITELN(max);
END.
板凳
fly100 [专家分：50] 发布于 2007-08-28 08:32:00
楼上的大牛,先谢谢拉+20分.
不过有分析吗,貌似看起来......
3 楼
fly100 [专家分：50] 发布于 2007-08-28 08:42:00
还有,注意数据规模,0<=n<=5000 ,1<=L,W<=30000
用一个二维数组 还是 BOOLEAN 貌似.......
4 楼
fly100 [专家分：50] 发布于 2007-08-28 08:46:00
还有,此题的时间限制虽长,但每个测试点也就1S,你用了6重FOR循环,这貌似....
5 楼
Matodied [专家分：7560] 发布于 2007-08-30 15:15:00
这a数组是存放一个位置能不能建浴场（这里有没有产奶点），能就是TRUE，不能就是FALSE。
不过你说的也对，BOOLEAN数组最多只能有65 535个元素，而你的面积最大值30 000*30 000=900 000 000了，这么大的面积数组是存不下的。
但是不用数组咋办呢？
6 楼
abcwuhang [专家分：1840] 发布于 2007-08-31 12:06:00
理所当然想到动规~~~
7 楼
fly100 [专家分：50] 发布于 2007-08-31 15:39:00
楼上的大虾,先给你加分了~~~,那你能不能再讲讲~~`
8 楼
cmy28 [专家分：380] 发布于 2007-09-01 12:03:00
动归是肯定的！！但是你得样例是不是有问题？怎么达到80呢？顶多64 啊！！
9 楼
fly100 [专家分：50] 发布于 2007-09-09 08:58:00
样例没有问题,那么多人都过了..........
10 楼
wyc4662 [专家分：0] 发布于 2009-07-24 16:34:00
但是产奶点可以位于浴场的轮廓上
注意这句话
我来回复
您所在位置：