ac1135.pas

某牛人写的acm.tongji.edu.cn上大部分ac的代码,仅供学习研究,请不要用来作弊

program tju1135;
const
  maxl=500001;
  maxwordlen=20;
  maxwords=15;
  maxtrie=maxwordlen*maxwords;
var
  door:array[1..maxl]of char;
  trie:array[0..maxtrie,'@'..'Z']of word;
  energy:array[1..maxtrie]of longint;
  dpreach,dpcost:array[1..maxwordlen]of longint;
  len,n,i,j,p,m,reach,cost,tcost:longint;
  c:char;
begin
  repeat
    inc(len);readln(door[len]);
  until door[len]='.';
  door[len]:='@';

  repeat
    fillchar(trie,sizeof(trie),0);
    fillchar(energy,sizeof(energy),0);
    read(n);j:=0;
    for i:=1 to n do begin
      readln(cost);p:=0;
      repeat
        read(c);
        if trie[p,c]=0 then begin inc(j);trie[p,c]:=j;end;
        p:=trie[p,c];
      until seekeoln;
      energy[p]:=cost;
    end;

    for i:=len downto 1 do begin
      p:=0;reach:=i-1;cost:=0;j:=i;
      while trie[p,door[j]]>0 do begin
        p:=trie[p,door[j]];inc(j);
        if energy[p]>0 then begin
          m:=j mod maxwordlen;
          tcost:=energy[p]+dpcost[m];
          if (dpreach[m]>reach) or (dpreach[m]=reach) and (tcost<cost) then begin
            reach:=dpreach[m];cost:=tcost;
          end;
        end;
      end;
      m:=i mod maxwordlen;
      dpreach[m]:=reach;dpcost[m]:=cost;
    end;
    writeln(dpcost[1]);
  until seekeof;
end.