讨论 / 求助 此题能用动态规划解吗
zlqiszlq 2008-07-11 03:38:00
点我顶贴 收藏 删除
先让点按x排序,然后预处理好low[i,j]表示i-j个点中y

值最小的,还有high[i,j]

再令f[i,j]表示第j个点用i个矩形覆盖所需的最小面积

状态转移方程是

f[i,j]=max{f[i-1,k]+S(k+1,j)}S表示从k+1个点到j各点的矩形面积

还有矩形边不能重合也处理了

但结果是4 5两个点过不了

源程序如下:

var

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

i,j,k,n,g,min,min1,min2:longint;

d:array[1..50]of boolean;

f:array[1..4,0..50] of record

n,low,high:longint;

end;

Low,high:array[1..50,1..50]of longint;

pp:boolean;

procedure qs(s,t:longint);

var

i,j,z1,z2:longint;

begin

i:=s;

j:=t;

z1:=x[i];

z2:=y[i];

while i<j do

begin

while ((i<j)and(z1<x[j]))or((i<j)and(z1=x[j])and(z2<y[j])) do

dec(j);

if i<j

then begin

x[i]:=x[j];

y[i]:=y[j];

inc(i);

end;

while ((i<j)and(x[i]<z1))or((i<j)and(z1=x[i])and(y[i]<Z2)) do

inc(i);

if i<j

then begin

x[j]:=x[i];

y[j]:=y[i];

dec(j);

end;

end;

x[i]:=z1;

y[i]:=z2;

if i-1>s

then qs(s,i-1);

if j+1<t

then qs(j+1,t);

end;

function ai(i,j:longint):longint;

begin

ai:=(high[i,j]-low[i,j])*(x[j]-x[i]);

end;

procedure init;

var

i,j,k,min,max:longint;

begin

fillchar(d,sizeof(d),true);

readln(n,g);

for i:=1 to n do

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

qs(1,n);

for i:=1 to n-1 do

if x[i]=x[i+1]

then d[i]:=false;

for i:=1 to n do

for j:=i to n do

begin

min:=123456789;

max:=-123456789;

for k:=i to j do

begin

if y[k]>max

then max:=y[k];

if y[k]<min

then min:=y[k];

end;

low[i,j]:=min;

high[i,j]:=max;

end;

for i:=1 to n do

begin

f[1,i].n:=ai(1,i);

f[1,i].high:=high[1,i];

f[1,i].low:=low[1,i];

end;

end;

begin

init;

for i:=2 to n do

for j:=2 to g do

begin

min:=123456789;

for k:=1 to i-1 do

begin

pp:=true;

if not(d[k])

then if (low[k+1,i]<=f[j-1,k].high)or(high[k+1,i]>=f[j-1,k].low)

then pp:=false;

if pp

then if ai(k+1,i)+f[j-1,k].n<min

then begin

min:=ai(k+1,i)+f[j-1,k].n;

min1:=high[k+1,i];

min2:=low[k+1,i];

end;

end;

f[j,i].n:=min;

f[j,i].high:=min1;

f[j,i].low:=min2;

end;

writeln(f[g,n].n);

end.

#1 181818181818@2008-07-11 03:38:00
回复 删除
似乎是分治
查看更多回复
提交回复