program dd;

var x,y:array[1..50] of longint;

i,j,k,l,m,n,s,sum,ans,x1,x2,y1,y2,min,o:longint;

procedure qsort1(v,w:longint);

var g,t,s,l,r:longint;

begin

t:=x[(v+w) div 2];l:=v;r:=w;

s:=y[(v+w) div 2];

repeat

while (x[l]s)) do dec(r);

if lr;

if l

没看出怎么DP,所以搜索

对每个点所在的矩形进行枚举.

去掉不符合的方案.然后统计.

据说没有k=4的情况,

所以50^3=125000完全可行.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

还好数据比较弱..没有K=4的情况...

枚举做的 214行超WS程序 =.=！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

郁闷.dp

交了两次………………

错误找了半天…………

才发现快排写挂了……

500.....用快排...下次不这样了..

数据太弱了

跑这个点：

50 4

1 1

2 2

...

50 50

就TLE，别谈秒杀了。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

type

sh=record

x1,y1,x2,y2:longint;

end;

var

n,k,ans,temp,i,j:longint;

x,y:array[1..50] of longint;

area:array[1..4] of sh;

procedure min(var a,b:longint);

begin

if a>b

then a:=b;

end;

procedure max(var a,b:longint);

begin

if a

搜索果然是万能的，按点搜索每次枚举放在第j个矩形中

LX的DP更牛···切割法···ORZ超长程序

搜索啦

program noipg4;

type

tlim=array[1..4,1..4] of integer; //k xmax,xmin,ymax,ymin

var

n,k,i,smin,s:longint;

x,y:array[1..50] of integer;

lim2:tlim;

bc:boolean;

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

begin

if a>b then max:=a else max:=b;

end;

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

begin

if alim1)and(lim1>lim1) then

s:=s+(lim1-lim1)*(lim1-lim1);

bc:=true;

for i:=1 to k-1 do

for j:=i+1 to k do

if (lim1>=lim1[j,4])and(lim1>=lim1[j,2])and(lim1

裸搜，一点也不费时，全0ms

var

n,k,i :longint;

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

procedure qsort(p,x1,y1:longint);

var

i,j,z :longint;

begin

i:=x1;

j:=y1;

z:=(x+x[j,p])shr 1;

while i=en then exit(0);

qsort(1,st,en);

s:=maxlongint;

for i:=st to en do

if x=x then continue else

s:=min(qiu(st,i)+qiu(i+1,en),s);

qsort(2,st,en);

for i:=st to en do

if x=x then continue else

s:=min(s,qiu(st,i)+qiu(i+1,en));

exit(s);

end;

function k3:longint;

var

s,i :longint;

begin

qsort(1,1,n);

s:=maxlongint;

for i:=1 to n do

s:=min(qiu(1,i)+k2(i+1,n),min(s,qiu(i+1,n)+k2(1,i)));

qsort(2,1,n);

for i:=1 to n do

s:=min(qiu(1,i)+k2(i+1,n),min(s,qiu(i+1,n)+k2(1,i)));

exit(s);

end;

begin

read(n,k);

for i:=1 to n do read(x,x);

if k=1 then writeln(qiu(1,n));

if k=2 then writeln(k2(1,n));

if k=3 then writeln(k3);

end.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

枚举不完了，疯了，K=4都不带考虑的，，，，，

可以看看枚举的程序多么恶心····

program asd;

type

arr=array[1..52]of integer;

var

ad:longint;

xpai,ypai:arr;

dian:array[1..52]of record

x,y:integer; end;

i,n,num:integer;

procedure xx(l,r:integer);

var

i,j,x,y:integer;

begin

i:=l;j:=r;x:=dian[xpai[(i+j)div 2]].x;

repeat

while dian[xpai[i]].xx do dec(j);

if ij;

if is then max:=s;

end; chuli:=max;

end;

end;

end;

begin

readln(n,num);

for i:=1 to n do

begin

readln(dian[i].x,dian[i].y);

xpai[i]:=i;ypai[i]:=i;end;

xx(1,n);yy(1,n);

ad:=chuli(xpai,ypai,1,n,num);writeln(ad);

end.

从1搜到50...超时了>..

但从50搜到1就过了...

还是倒着比较好啊>...

搜索。

如果当前矩形大小大于当前最优解，exit。[最优性质剪枝]

如果有重叠，exit。[可行性剪枝]

写了一百行左右。

0ms

DFS+可行性剪枝+最优性剪枝 难道还有比这更经典的搜索方式吗？

void search(int K,int x0,int x1,int y0,int y1,int s)

还要分几块，剩下要分割的领域描述，当前已用掉的面积

{

if(K==1)

{

直接计算 [注意:如果此时该领域无点,则该情况不成立,忽略]

更新r

}

else

{

从上面切下来一个矩形, search(K-1,...) [注意:该矩形下边界有很多点的话,宽度应该计算所有这些点的]

从下面

从左面

从右面

}

}

输入数据

排序,分别按x和y

search(k,0,500,0,500,0);

输出 r

k=1时，很简单，不说了。

k=2时，将所有点按横坐标排序，用一条平行与y轴的直线将所有点分为两部分，分别用一个矩形覆盖，可得到一个解。枚举所有这样的划分方案进行求解（即对点进行枚举，用每个点及其后一个点之间的直线划分）。再按纵坐标排序，用平行与x轴的直线划分，同样方法求解。最后得到最优解。

k=3时，类似于k=2时的情况。只是划分后，一部分用一个矩形覆盖，另一部分用两个矩形覆盖，并求解。然后颠倒过来再求解。

k=4时，简单地用直线划分不一定能求得最优解（如右图，其最优解是零）。我的算法是枚举每个点，将它以及它左下方（包括正左方和正下方）的点用一个矩形覆盖，而其余的点用三个矩形覆盖。。

好猥琐啊...我抄wjd的代码分k=1,2,3,4讨论的...累死我了...

#include

using namespace std;

int x[60],y[60],k,n,lx=0,ly=0;

int ax[60],ay[60];

int hx[510],hy[510];

void init()

{

memset(hx,0,sizeof(hx));

memset(hy,0,sizeof(hy));

cin>>n>>k;

for (int i=1;i>xt>>yt;

hx[xt]=1;ax[i]=xt;

hy[yt]=1;ay[i]=yt;

}

for (int i=0;i

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

DP 可以吧。。

裸搜~~

忽忽~Puppy无敌！！