其实这题二分+dp就能过，但还有另一种用trie的方法，第一种是枚举所有能变化的字符串，然后再暴力剪枝在trie找
但是第二种跑的特别快，是在trie上DFS，省去了很多步骤
1 var 2 bo:array[-1..200000] of longint; 3 s:array[-1..200000,0..25] of longint; 4 f:array[0..25000] of longint; 5 ss:array[0..25000] of string; 6 now,tmp,ans,root,i,j,k,n,x,sum:longint; 7 function max(x,y:longint):longint; 8 begin 9 if x>y then 10 exit(x) 11 else exit(y); 12 end; 13 procedure insert(s1:string;len,num:longint); 14 var 15 i,fa,tmp:longint; 16 begin 17 fa:=root; 18 for i:=1 to len do 19 begin 20 x:=ord(s1[i])-97; 21 if (x<0)or(x>25) then 22 exit; 23 if s[fa,x]=0 then 24 begin 25 inc(sum); 26 s[fa,x]:=sum; 27 tmp:=sum; 28 end 29 else tmp:=s[fa,x]; 30 fa:=tmp; 31 end; 32 bo[sum]:=num; 33 end; 34 function find(fa:longint;s1:string):longint; 35 var 36 i:longint; 37 begin 38 k:=length(s1); 39 for i:=1 to k do 40 begin 41 x:=ord(s1[i])-97; 42 if s[fa,x]<>0 then 43 fa:=s[fa,x] 44 else exit(0); 45 end; 46 find:=fa; 47 end; 48 procedure solve(s:string;num:longint); 49 var 50 s1,s2:string; 51 i,k,tmp:longint; 52 begin 53 k:=length(s); 54 for i:=1 to k do 55 begin 56 s1:=copy(s,1,i-1); 57 s2:=copy(s,i+1,k-i); 58 now:=find(root,s1); 59 for j:=ord(s[i])-97 downto 1 do 60 begin 61 tmp:=bo[find(now,chr(j+96)+s2)]; 62 if tmp<>0 then 63 f[num]:=max(f[num],f[tmp]+1); 64 end; 65 if s1+s2>s then continue; 66 tmp:=bo[find(now,s2)]; 67 if tmp<>0 then 68 f[num]:=max(f[num],f[tmp]+1); 69 end; 70 for j:=0 to k-1 do 71 begin 72 s1:=copy(s,1,j); 73 s2:=copy(s,j+1,k-j); 74 now:=find(root,s1); 75 for i:=1 to 26 do 76 begin 77 if s1+chr(i+96)+s2<s then 78 begin 79 tmp:=bo[find(now,chr(i+96)+s2)]; 80 if tmp<>0 then 81 f[num]:=max(f[num],f[tmp]+1); 82 end; 83 end; 84 end; 85 end; 86 begin 87 sum:=0; 88 n:=0; 89 root:=-1; 90 while not eof do 91 begin 92 inc(n); 93 readln(ss[n]); 94 insert(ss[n],length(ss[n]),n); 95 f[n]:=1; 96 end; 97 for i:=2 to n do 98 solve(ss[i],i); 99 ans:=0; 100 for i:=1 to n do 101 if ans<f[i] then 102 ans:=f[i]; 103 writeln(ans); 104 end.
500ms+
1 var 2 l:array[-1..200000] of longint; 3 s:array[-1..200000,0..25] of longint; 4 f:array[0..25000] of longint; 5 ss:array[0..25000] of string; 6 top,maxx,ans,root,i,j,k,n,x,sum:longint; 7 function max(x,y:longint):longint; 8 begin 9 if x>y then 10 exit(x) 11 else exit(y); 12 end; 13 procedure insert(s1:string;len:longint); 14 var 15 i,fa:longint; 16 begin 17 fa:=root; 18 for i:=1 to len do 19 begin 20 x:=ord(s1[i])-97; 21 if (x<0)or(x>25) then 22 exit; 23 if s[fa,x]=0 then 24 begin 25 inc(sum); 26 s[fa,x]:=sum; 27 fa:=sum; 28 end 29 else fa:=s[fa,x]; 30 end; 31 l[fa]:=n; 32 end; 33 34 procedure solve(len,x:longint;bo:boolean); 35 var 36 i:longint; 37 begin 38 if (len=k) then 39 begin 40 if (l[x]<>0)and(l[x]<>n) then 41 f[n]:=max(f[n],f[l[x]]+1); 42 exit; 43 end; 44 if (s[x,ord(ss[n][len+1])-97]<>0) then 45 solve(len+1,s[x,ord(ss[n][len+1])-97],bo); 46 if bo=true then 47 begin 48 for i:=0 to 25 do 49 if s[x,i]<>0 then 50 begin 51 if i<=ord(ss[n][len+1])-97 then 52 solve(len,s[x,i],false);//insert 53 if i<ord(ss[n][len+1])-97 then 54 solve(len+1,s[x,i],false);//change 55 end; 56 solve(len+1,x,false);//delete 57 end; 58 end; 59 begin 60 sum:=0; 61 n:=0; 62 root:=0; 63 ans:=0; 64 while not eof do 65 begin 66 inc(n); 67 readln(ss[n]); 68 k:=length(ss[n]); 69 insert(ss[n],k); 70 f[n]:=1; 71 solve(0,root,true); 72 end; 73 for i:=1 to n do 74 if ans<f[i] then 75 ans:=f[i]; 76 writeln(ans); 77 end.
100ms+