ac1087.pas

同济大学 Online在线题库 AC源代码合集 程序设计竞赛必看资料

program tju1087;
const
  maxd=100;
  maxn=100;
  initial=10;
type
  garbage=record time:word;life,height:byte;end;
var
  g:array[1..maxn]of garbage;
  l:array[boolean,0..maxd-1]of integer;
  d,n,i,j,t,m,m1:shortint;
  tg:garbage;
procedure update(var a:integer;b:integer);
  begin
    if b>a then a:=b;
  end;
procedure climb;
  begin
    fillchar(l[false],sizeof(l[false]),255);
    l[false,0]:=initial;m:=0;
    for i:=1 to n do begin
      fillchar(l[odd(i)],sizeof(l[odd(i)]),255);m1:=-1;
      for j:=m downto 0 do
        if l[not odd(i),j]>=g[i].time then begin
          t:=j+g[i].height;
          if t>=d then begin
            writeln(g[i].time);exit;
          end
          else begin
            update(l[odd(i),t],l[not odd(i),j]);
            if t>m1 then m1:=t;
          end;
          update(l[odd(i),j],l[not odd(i),j]+g[i].life);
        end;
      if l[odd(i),0]<0 then begin
        writeln(l[not odd(i),0]);
        exit;
      end;
      m:=m1;
    end;
    writeln(l[odd(i),0]);
  end;
begin
  repeat
    read(d,n);
    for i:=1 to n do
      with g[i] do read(time,life,height);
    for i:=1 to n-1 do
      for j:=i+1 to n do
        if g[i].time>g[j].time then begin
          tg:=g[i];g[i]:=g[j];g[j]:=tg;
        end;
    climb;
  until seekeof;
end.