ac1063.pas

这是在网络上搜集到的在东京大学的ACM上面解决的一些题目的源码

program tju1063;
const
  maxw=100;
  maxn=7;
  maxvalue=2500;
var
  v,min,max:array[1..maxn]of byte;
  len:array[-1..maxw]of integer;
  sum:array[-1..maxw,0..maxvalue]of shortint;
  w,n,i,j,k,s,t,m:integer;
begin
  repeat
    read(w,n);
    for i:=1 to n do
      read(v[i],min[i],max[i]);

    fillchar(sum,sizeof(sum),0);
    len[-1]:=-1;sum[0,0]:=1;
    for i:=1 to w do begin
      m:=0;
      for j:=1 to n do begin
        if i<min[j] then continue;
        t:=i-min[j];s:=i-max[j]-1;if s<-1 then s:=-1;
        for k:=0 to len[t] do
          if sum[t,k]>sum[s,k] then sum[i,k+v[j]]:=1;
        if len[t]+v[j]>m then m:=len[t]+v[j];
      end;
      if i=w then break;
      len[i]:=m;
      for j:=0 to m do
        inc(sum[i,j],sum[i-1,j]);
    end;

    s:=0;
    for i:=1 to m do
      if sum[w,i]=1 then inc(s);
    writeln(s);
  until seekeof;
end.