POJ2392

題意:奶牛們要用K個不同類型的石頭建太空電梯.每一種石頭的高度為Hi，數量為Ci,且不能放在高于Ai的地方,求最高能建多高的太空電梯.

分析:多重背包,數組標記.顯然將ai小的放在下面會更優.所以先排序.

code:

const maxh=41000;
var   cnt:array[0..maxh] of longint;h,a,c:array[0..401] of longint;f:array[0..maxh] of boolean;n,i,j,k,tmp,ans:longint;procedure swap(var a,b:longint);var   tmp:longint;begintmp:=a; a:=b; b:=tmp;end;procedure sort(l,r:longint);var   i,j,mid:longint;begini:=l; j:=r;mid:=a[(l+r)>>1];while i<=j dobeginwhile a[i]<mid do inc(i);while a[j]>mid do dec(j);if i<=j thenbeginswap(h[i],h[j]);swap(a[i],a[j]);swap(c[i],c[j]);inc(i); dec(j);end;end;if i<r then sort(i,r);if j>l then sort(l,j);end;beginreadln(n);for i:=1 to n do readln(h[i],a[i],c[i]);sort(1,n);f[0]:=true;for i:=1 to n dobeginfillchar(cnt,sizeof(cnt),0);for j:=0 to a[i] doif (f[j]=true)and(not f[j+h[i]])and(j+h[i]<=a[i])and(cnt[j]<c[i]) thenbeginf[j+h[i]]:=true;cnt[j+h[i]]:=cnt[j]+1;end;end;for i:=maxh downto 0 do if f[i] then break;writeln(i);end.