状态: Unaccepted

测评机： Xeond[6]

得分： 20分

提交日期： 2012-7-31 9:08:00

有效耗时： 312毫秒

测试结果1:

测试结果2: 通过本测试点|有效耗时156ms

测试结果3: 运行错误|栈溢出

测试结果4: 运行错误|栈溢出

测试结果5:

测试结果6:

测试结果7: 通过本测试点|有效耗时156ms

测试结果8: 运行错误|栈溢出

测试结果9: 运行错误|栈溢出

测试结果10:

//基本思路是暴搜

type

jx=record

x1,y1,x2,y2:longint;

end;

arr=array[1..4] of jx;

var

zq,n,m,i:longint;

sj:arr;

a:array[1..50,1..2] of longint;

function calc(k:longint; sj:arr):longint;

begin

calc:=0;

for i:=1 to k do

calc:=calc+(sj[i].x2-sj[i].x1)*(sj[i].y2-sj[i].y1);

end;

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

begin if a<b then exit(a); exit(b); end;

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

begin if a>b then exit(a); exit(b); end;

procedure sou(t,k:longint; sj:arr);

var sd:arr;

area,x,y,i,j,xx1,xx2,xx3,xx4,yy1,yy2,yy3,yy4,xxx1,xxx2,xxx3,xxx4,yyy1,yyy2,yyy3,yyy4:longint;

ok:boolean;

begin

area:=calc(k,sj);

if area>=zq then exit;

if t>n then

begin

//if k=m then

zq:=area;

exit;

end;

x:=a[t,1]; y:=a[t,2];

for i:=1 to k do

if ( x >= sj[i].x1 ) and ( x <= sj[i].x2 ) then

if ( y >=sj[i].y1 ) and ( y <= sj[i].y2 ) then

begin

sou(x+1,k,sj);

exit;

end;

if k<m then

begin

inc(k);

sj[k].x1:=x; sj[k].x2:=x;

sj[k].y1:=y; sj[k].y2:=y;

sou(t+1,k,sj);

dec(k);

end;

for i:=1 to k do begin

xx1:=min(sj[i].x1,x); yy1:=min(sj[i].y1,y);

xx2:=max(sj[i].x2,x); yy2:=max(sj[i].y2,y);

xx3:=xx1; yy3:=yy2;

xx4:=xx2; yy4:=yy1;

ok:=true;

for j:=1 to k do //panduan shi fou you chonghe

if i=j then continue

else

begin

xxx1:=sj[j].x1; yyy1:=sj[j].y1;

xxx2:=sj[j].x2; yyy2:=sj[j].y2;

xxx3:=xxx1; yyy3:=yyy2;

xxx4:=xxx2; yyy4:=yyy1;

if (xx1>=xxx1) and (xx1<=xxx2) and (yy1>=yyy1) and (yy1<=yyy2) then begin ok:=false; break; end;

if (xx2>=xxx1) and (xx2<=xxx2) and (yy2>=yyy1) and (yy2<=yyy2) then begin ok:=false; break; end;

if (xx3>=xxx1) and (xx3<=xxx2) and (yy3>=yyy1) and (yy3<=yyy2) then begin ok:=false; break; end;

if (xx4>=xxx1) and (xx4<=xxx2) and (yy4>=yyy1) and (yy4<=yyy2) then begin ok:=false; break; end;

if (xxx1>=xx1) and (xxx1<=xx2) and (yyy1>=yy1) and (yyy1<=yy2) then begin ok:=false; break; end;

if (xxx2>=xx1) and (xxx2<=xx2) and (yyy2>=yy1) and (yyy2<=yy2) then begin ok:=false; break; end;

if (xxx3>=xx1) and (xxx3<=xx2) and (yyy3>=yy1) and (yyy3<=yy2) then begin ok:=false; break; end;

if (xxx4>=xx1) and (xxx4<=xx2) and (yyy4>=yy1) and (yyy4<=yy2) then begin ok:=false; break; end;

end;

if not ok then continue;

sd:=sj;

sd[i].x1:=xx1; sd[i].x2:=xx2;

sd[i].y1:=yy1; sd[i].y2:=yy2;

sou(t+1,k,sd);

end;

end;

begin

readln(n,m);

for i:=1 to n do

readln(a[i,1],a[i,2]);

if n=1 then

begin

writeln(0);

halt;

end;

sj[1].x1:=a[1,1];

sj[1].y1:=a[1,2];

sj[1].x2:=a[1,1];

sj[1].y2:=a[1,2];

zq:=maxlongint;

sou(2,1,sj);

writeln(zq);

end.

我check出来了。。。是该死的变量问题

话说这题其实不难呐 k=4也是完全能过的。

用dfs(s,k)表示点的集合s用k个矩阵覆盖的最小面积和即可。

每次枚举集合里头一个点,然后从这个点横向或纵向切开

dfs(s,k)=MIN(dfs(s1,1)+dfs(s2,k-1)) 复杂度约为50^4