P1019 单词接龙

 1 program no; 2 uses math; 3 const 4   inf=‘test.in‘; 5   outf=‘test.out‘; 6 var 7    a:array[1..20] of string; 8    i,j,n,tot,ans:longint; 9    f:array[1..20,1..20] of longint;10    ex:array[1..20] of longint;11    tt:char;  12    13 procedure compare(aa,bb:longint);14 var15   i,j,lena,lenb,k:longint;16 begin17   lenb:=length(a[bb]);18   lena:=length(a[aa]);19   k:=maxlongint;20   for j:= lena downto 1 do21     if a[aa,j]=a[bb,1] then22      if copy(a[aa],j,lena-j+1)=copy(a[bb],1,lena-j+1) then23        if (lena-j+1=min(lena,lenb)) then  //如果有包含关系24             begin  if aa<>bb then exit; end //排除自己接自己25        else begin26               k:=min(k,lena-j+1);27               break;//优化28             end;29 30   if k<>maxlongint then31     f[aa,bb]:=lenb-k;//记录延长的长度32 end;33 34 procedure search(i:Longint);  //dfs35 var36   j:longint;37 begin38     for j:= 1 to n do39       if ex[j]>-2 then  //如果还有可以用的次数40         if f[i,j]<>0 then  //如果不是白接41         begin42           // writeln(i,‘ ‘,j,‘ ‘,f[i,j]);43             tot:=tot+f[i,j];44             dec(ex[j]);45             search(j);46             tot:=tot-f[i,j];47             inc(ex[j]);48         end;49     if ans<tot then ans:=tot;50 end;51 52 begin53     //assign(input,inf);  assign(output,outf);54     reset(input); rewrite(output);55 56     readln(n);57     for i:= 1 to n do58       readln(a[i]);59     for i:= 1 to n do60       for j:= 1 to n do61         compare(i,j);62     readln(tt);63     for i:= 1 to n do    //枚举开头的串64       if tt=a[i,1] then65       begin66         fillchar(ex,sizeof(ex),0);67         tot:=length(a[i]);68         dec(ex[i]);69         search(i);70       end;71     writeln(ans);72     close(input);  close(output);73 end.