ac1247.pas

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

program tju1247;
const
  maxn=100;
  maxcount=100;
var
  price:array[1..maxn]of word;
  count:array[1..maxn]of byte;
  cost:array[0..maxcount]of int64;
  k,n,i,modulo,cheap,x,d:longint;
  inf,p,t,ans,extra:int64;
function gcd(a,b:longint):longint;
  var
    t:longint;
  begin
    if a<b then begin t:=a;a:=b;b:=t;end;
    repeat
      t:=a mod b;a:=b;b:=t;
    until b=0;
    gcd:=a;
  end;
begin
  inf:=maxlongint;inf:=sqr(inf);
  repeat
    read(k,n);read(price[1],count[1]);x:=count[1];
    for i:=2 to n do begin
      read(price[i],count[i]);
      x:=gcd(x,count[i]);
    end;
    for i:=1 to n do
      count[i]:=count[i] div x;
    k:=k div x+ord(k mod x>0);

    modulo:=0;
    for i:=1 to n do begin
      if count[i]>modulo then modulo:=count[i];
      if (i=1) or (count[i]*price[cheap]>count[cheap]*price[i]) or
         (count[i]*price[cheap]>count[cheap]*price[i]) and
         (count[i]<count[cheap]) then cheap:=i;
    end;

    ans:=inf;extra:=0;x:=0;cost[0]:=0;d:=0;
    repeat
      inc(x);p:=inf;
      for i:=1 to n do begin
        if x<count[i] then continue;
        t:=cost[(x-count[i]) mod modulo]+price[i];
        if t<p then p:=t;
      end;
      if (x>=count[cheap]) and (x<k) then begin
        if (p-cost[(x-count[cheap]) mod modulo]=price[cheap]) then inc(d) else d:=0;
        if d=count[cheap] then begin
          d:=(k-x) div count[cheap];
          extra:=int64(price[cheap])*d;dec(k,count[cheap]*d);
          d:=0;
        end;
      end;
      cost[x mod modulo]:=p;
      if x>=k then if p<ans then ans:=p;
    until x=k+modulo-1;
    writeln(ans+extra);
  until seekeof;
end.