poj2392

首先按限制高度排序，然后按多重背包做dp
这里的背包只用知道每种状态是否可行，所以
这里的多重背包可以变成O(nm)
  1 const max=30000001;
  2 var f:array[0..1,0..1010,0..4] of longint;
  3     a,b:array[0..1010] of longint;
  4     i,j,k1,k2,n,k,m,w,ans,t:longint;
  5 function findmin(t:longint):longint;
  6   var p,k:longint;
  7   begin
  8     p:=max;
  9     for k:=1 to 4 do
 10       p:=min(p,f[k1,j-t,k]);
 11     exit(p);
 12   end;
 13 procedure sort(l,r: longint); //按列排序，上下都有牛时1在前2在后，这样处理dp的时候方便多
 14   var i,j,x,y: longint;
 15   begin
 16     i:=l;
 17     j:=r;
 18     x:=a[(l+r) div 2];
 19     y:=b[(l+r) div 2];
 20     repeat
 21       while (a[i]<x) or (a[i]=x) and (b[i]<y) do inc(i);
 22       while (x<a[j]) or (a[j]=x) and (b[j]>y) do dec(j);
 23       if not(i>j) then
 24       begin
 25         swap(a[i],a[j]);
 26         swap(b[i],b[j]);
 27         inc(i);
 28         j:=j-1;
 29       end;
 30     until i>j;
 31     if l<j then sort(l,j);
 32     if i<r then sort(i,r);
 33   end;
 34 
 35 procedure doit1;
 36   begin
 37     f[k2,j,1]:=min(f[k2,j,1],f[k1,j,1]+2*(a[i]-a[i-1]));
 38     f[k2,j,1]:=min(findmin(1)+2,f[k2,j,1]);
 39   end;
 40 
 41 procedure doit2;
 42   var p:longint;
 43   begin
 44     f[k2,j,2]:=min(f[k1,j,2]+2*(a[i]-a[i-1]),f[k2,j,2]);
 45     p:=min(min(f[k1,j-1,2],f[k1,j-1,3]),f[k1,j-1,4]);
 46     f[k2,j,2]:=min(f[k2,j,2],p+a[i]-a[i-1]+1);
 47     if j-2>=0 then
 48       f[k2,j,2]:=min(f[k2,j,2],findmin(2)+2);
 49   end;
 50 
 51 procedure doit(x:longint);
 52   var p:longint;
 53   begin
 54     p:=min(f[k1,j,x],f[k1,j,2]);
 55     f[k2,j,x]:=min(f[k2,j,x],p+a[i]-a[i-1]);
 56     f[k2,j,x]:=min(f[k2,j,x],findmin(1)+1);
 57   end;
 58 
 59 begin
 60   readln(n,k,m);
 61   for i:=1 to n do
 62     readln(b[i],a[i]);
 63   sort(1,n);
 64   for i:=0 to k do  //初始化
 65     for j:=1 to 4 do
 66     begin
 67       f[0,i,j]:=max;
 68       f[1,i,j]:=max;
 69     end;
 70   i:=1;
 71   f[0,1,1]:=2;
 72   if a[i]=a[i+1] then
 73   begin
 74     i:=3;
 75     f[0,2,2]:=2;
 76   end
 77   else begin
 78     i:=2;
 79     if b[1]=1 then f[0,1,3]:=1
 80     else f[0,1,4]:=1;
 81   end;
 82   k1:=1;
 83   k2:=0;
 84   while i<=n do
 85   begin
 86     k1:=k1 xor 1; //滚动数组
 87     k2:=k2 xor 1;
 88     if a[i]=a[i+1] then w:=2 else w:=1;
 89     for j:=1 to k do
 90     begin
 91       for t:=1 to 4 do
 92         f[k2,j,t]:=max;
 93       doit1;  //做4个状态，方程式自己动手比划一下就明白了
 94       doit2;
 95       if w=1 then
 96       begin
 97         if b[i]=1 then
 98           doit(3)
 99         else doit(4);
100       end;
101     end;
102     i:=i+w;
103   end;
104   ans:=max;
105   for i:=1 to 4 do
106     ans:=min(ans,f[k2,k,i]);
107   writeln(ans);
108 end.
View Code
注意：一般的多重背包复杂度到O(nm)必须使用单调队列，这里是特殊情况