学步园

【题意】

有n头牛在2*b的牧场上，只可以修建k(k<=n)个矩形牛棚，牛棚之间不能有重叠的部分，求牛棚的最小面积

【输入】

第一行n、k、b

【输出】

最小面积

状压dp

离散一下，用0~3表示这一列的状态

然后dp，f[i][j][k]表示第i列用了j个牛棚，状态为k的最小面积

k分为0~4，表示

0：什么也没有

1：上面一格被覆盖

2：下面一个被覆盖

3：两格被同一个矩形覆盖

4：两格被不同的矩形覆盖

program poj2430;
var
  inf,tot,n,k,b,i,j:longint;
  st,x,y,p:array [0..1001] of longint;
  f:array [0..1001,0..1001,0..4] of longint;
  mini:array [0..1001,0..1001] of longint;

procedure swap (var a,b:longint);inline;
begin
  if a=b then exit;
  b:=a xor b;
  a:=a xor b;
  b:=a xor b;
end;

function min (a,b,c,d:longint):longint;inline;
var
  ans:longint;
begin
  ans:=a;
  if b<ans then ans:=b;
  if c<ans then ans:=c;
  if d<ans then ans:=d;
  exit(ans);
end;

procedure qsort (s,e:longint);
var
  i,j,q,p:longint;
begin
  if s>=e then exit;
  i:=s;
  j:=e;
  q:=x[(s+e) div 2];
  p:=y[(s+e) div 2];
  while i<=j do
    begin
      while (y[i]<p)or((y[i]=p)and(x[i]<q)) do inc(i);
      while (y[j]>p)or((y[j]=p)and(x[j]>q)) do dec(j);
      if i>j then break;
      swap(x[i],x[j]);
      swap(y[i],y[j]);
      inc(i);
      dec(j);
    end;
  qsort(s,j);
  qsort(i,e);
end;

begin
  read(n,k,b);
  for i:=1 to n do
    read(x[i],y[i]);
  qsort(1,n);
  tot:=0;
  i:=1;
  while i<=n do
    if y[i]=y[i+1] then
      begin
        inc(tot);
        st[tot]:=3;
        p[tot]:=y[i];
        i:=i+2
      end
                   else
      begin
        inc(tot);
        st[tot]:=1 shl (x[i]-1);
        p[tot]:=y[i];
        inc(i);
      end;
  fillchar(f,sizeof(f),32);
  fillchar(mini,sizeof(mini),32);
  inf:=f[0,0,0];
  f[0,0,0]:=0;
  mini[0,0]:=0;
  p[0]:=-inf;
  for i:=1 to tot do
    for j:=1 to tot do
      case st[i] of
        1:begin
            f[i,j,1]:=min(f[i,j,1],
            f[i-1,j,1]+p[i]-p[i-1],
            f[i-1,j,4]+p[i]-p[i-1],
            mini[i-1,j-1]+1);

            f[i,j,3]:=min(f[i,j,3],
            f[i-1,j,3]+2*(p[i]-p[i-1]),
            mini[i-1,j-1]+2,
            inf);

            if j>1 then
            f[i,j,4]:=mini[i-1,j-2]+2;

            f[i,j,4]:=min(f[i,j,4],
            f[i-1,j,4]+2*(p[i]-p[i-1]),
            f[i-1,j-1,1]+(p[i]-p[i-1])+1,
            f[i-1,j-1,2]+(p[i]-p[i-1])+1);

            mini[i,j]:=min(f[i,j,1],
            f[i,j,2],
            f[i,j,3],
            f[i,j,4]);
          end;
        2:begin
            f[i,j,2]:=min(f[i,j,2],
            f[i-1,j,2]+p[i]-p[i-1],
            f[i-1,j,4]+p[i]-p[i-1],
            mini[i-1,j-1]+1);

            f[i,j,3]:=min(f[i,j,3],
            f[i-1,j,3]+2*(p[i]-p[i-1]),
            mini[i-1,j-1]+2,
            inf);

            if j>1 then
            f[i,j,4]:=mini[i-1,j-2]+2;

            f[i,j,4]:=min(f[i,j,4],
            f[i-1,j,4]+2*(p[i]-p[i-1]),
            f[i-1,j-1,1]+p[i]-p[i-1]+1,
            f[i-1,j-1,2]+p[i]-p[i-1]+1);

            mini[i,j]:=min(f[i,j,1],
            f[i,j,2],
            f[i,j,3],
            f[i,j,4]);
          end;
        3:begin
            f[i,j,3]:=min(f[i,j,3],
            mini[i-1,j-1]+2,
            f[i-1,j,3]+2*(p[i]-p[i-1]),
            inf);

            if j>1 then
            f[i,j,4]:=mini[i-1,j-2]+2;

            f[i,j,4]:=min(f[i,j,4],
            f[i-1,j,4]+2*(p[i]-p[i-1]),
            f[i-1,j-1,1]+p[i]-p[i-1]+1,
            f[i-1,j-1,2]+p[i]-p[i-1]+1);

            mini[i,j]:=min(f[i,j,1],
            f[i,j,2],
            f[i,j,3],
            f[i,j,4]);
          end;
      end;
  writeln(min(
  f[tot,k,1],
  f[tot,k,2],
  f[tot,k,3],
  f[tot,k,4]));
end.