tom的烦恼5ac.pas

背包类问题浅析和一些背包类问题的解答源程序。

Source CodeSource
Problem Id:1145  User Id:root 
Memory:288K  Time:510MS
Language:Pascal  Result:Accepted
  Source 
program tju1048;
const
  maxn=30000;
type
  jobtype=record from,till,money:cardinal;end;
var
  job:array[1..maxn]of jobtype;
  time,best:array[0..maxn*2]of cardinal;
  last:array[1..maxn*2]of word;
  pre:array[1..maxn]of word;
  u,n,i,times,x:cardinal;
procedure qsort(s,t:cardinal);
  var
    p,i,j,tmp:cardinal;
  begin
    if s>=t then exit;
    p:=s+random(t-s+1);
    tmp:=time[p];time[p]:=time[s];
    i:=s;j:=t;
    repeat
      while (i<j) and (time[j]>=tmp) do dec(j);
      if i=j then break;time[i]:=time[j];inc(i);
      while (i<j) and (time[i]<=tmp) do inc(i);
      if i=j then break;time[j]:=time[i];dec(j);
    until i=j;
    time[i]:=tmp;
    qsort(s,i-1);
    qsort(i+1,t);
  end;
function binsearch(x:cardinal):cardinal;
  var
    l,r,m:cardinal;
  begin
    l:=1;r:=times;
    repeat
      m:=(l+r) shr 1;
      if time[m]=x then break else if time[m]<x then l:=m+1 else r:=m-1;
    until false;
    binsearch:=m;
  end;
begin
    read(n);
    for i:=1 to n do begin
      read(job[i].from,job[i].till,job[i].money);
      time[i*2-1]:=job[i].from;time[i*2]:=job[i].till;
    end;
    qsort(1,n*2);
    times:=1;
    for i:=2 to n*2 do
      if time[i]>time[i-1] then begin
        inc(times);time[times]:=time[i];
      end;
 for i:=1 to n do
      with job[i] do begin
        from:=binsearch(from);till:=binsearch(till);
        pre[i]:=last[till];last[till]:=i;
      end;
    for i:=1 to times do begin
      best[i]:=best[i-1];
      while last[i]>0 do begin
        x:=best[job[last[i]].from]+job[last[i]].money;
        if x>best[i] then best[i]:=x;
        last[i]:=pre[last[i]];
      end;
    end; writeln(best[times]);
end.