Vijos 题解：http://hi.baidu.com/umule/item/2c997f8ed9600fdae596e017
有疑问请留言 共同进步

program p1028;
var
s:array[0..2000]of ansistring;
f:array[0..2000]of longint;
n:longint;
////////////////////////////////
procedure init;
var i:longint;
begin

readln(n);
for i:=1 to n do readln(s[i]);
end;
///////////////////////////////
procedure main;
var i,j:longint;
begin
for i:=1 to n do f[i]:=1;
for i:=2 to n do
for j:=1 to i-1 do
if (pos(s[j],s[i])=1) and (f[i]<f[j]+1) then f[i]:=f[j]+1;
end;
//////////////////////////////
procedure print;
var i,max:longint;
begin
max:=0;
for i:=1 to n do
if max<f[i] then max:=f[i];
writeln(max);

end;
/////////////////////////////
begin
init;
main;
print;
end.

...参见物理竞赛培优教程 运动学某例题...

注意要前缀不是简单的保函- =
var
nam:array[0..2001] of string;
r: array[0..2001] of longint;
n,i,j,k:longint;

begin
readln(n);
for i:=1 to n do begin
readln(nam[i]);
r[i]:=1;
end;
for i:=2 to n do
for j:=i-1 downto 1 do
if (pos(nam[j],nam[i])=1)and
(r[i]<r[j]+1) then
r[i]:=r[j]+1; j:=0;
for i:=1 to n do
if r[i]>j then
j:=r[i];
writeln(j);
end.

erep(i,1,n)
cin>>s[i];
int f[2222];
rep(i,1,2222)
f[i]=1;

int ans=1;
erep(i,1,n)
rep(j,1,i)
if(!s[i].find(s[j]))
f[i]=max(f[i],f[j]+1),ans=max(f[i],ans);

cout<<ans<<endl;

测试数据 #0: Accepted, time = 0 ms, mem = 1324 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 1324 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 1328 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 1324 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 1324 KiB, score = 10

测试数据 #5: Accepted, time = 0 ms, mem = 1324 KiB, score = 10

测试数据 #6: Accepted, time = 0 ms, mem = 1324 KiB, score = 10

测试数据 #7: Accepted, time = 15 ms, mem = 1324 KiB, score = 10

测试数据 #8: Accepted, time = 15 ms, mem = 1328 KiB, score = 10

测试数据 #9: Accepted, time = 93 ms, mem = 1324 KiB, score = 10

求dp瞬秒标程，鄙人的LIS 8点0s、剩余2点共90s，贴程序：
var
n,i,j:integer;
max:longint;
b:array[0..2000,1..2000]of boolean;
f:array[0..2000]of integer;
s:array[1..2000]of string[75];

begin
readln(n);
for i:=1 to n do readln(s[i]);

fillchar(b,sizeof(b),false);
for i:=1 to n-1 do
for j:=i+1 to n do
if copy(s[j],1,length(s[i]))=s[i] then b[i,j]:=true;
for i:=1 to n do b[0,i]:=true;

f[0]:=0;
for i:=1 to n do
begin
max:=-maxlongint;
for j:=0 to i-1 do
if b[j,i] then
if f[j]>max then max:=f[j];
f[i]:=max+1;
end;

max:=-maxlongint;
for i:=1 to n do
if f[i]>max then max:=f[i];
writeln(max);
end.
（一些不如法眼的小习惯略过。。。）大神求解==

点击查看程序源码+详细题解

用字符树+DFS查找，秒过的

var a:Array[1..2000] of string;

　　n,i,s,j,ans:longint;

　　str:string;

begin

readln(n);

for i:=1 to n do readln(a[i]);

for i:=1 to n do begin

　　s:=0;

　　for j:=1 to n do if length(a[i])>=length(a[j]) then begin

　　 str:=copy(a[i],1,length(a[j]));

　　 if str=a[j] then s:=s+1;

　　end;

　　if ans

编译通过... 

├ 测试数据 01：答案正确... (0ms, 31304KB) 

├ 测试数据 02：答案正确... (0ms, 31304KB) 

├ 测试数据 03：答案正确... (0ms, 31304KB) 

├ 测试数据 04：答案正确... (0ms, 31304KB) 

├ 测试数据 05：答案正确... (0ms, 31304KB) 

├ 测试数据 06：答案正确... (0ms, 31304KB) 

├ 测试数据 07：答案正确... (0ms, 31304KB) 

├ 测试数据 08：答案正确... (0ms, 31304KB) 

├ 测试数据 09：答案正确... (0ms, 31304KB) 

├ 测试数据 10：答案正确... (0ms, 31304KB) 

为保钓事业贡献出我们的0ms！！

用string类，然后直接调用系统函数find，我先自己写了个匹配的调用函数，超时，汗，还是系统函数好啊

字符串查找树+DFS

可惜了未秒杀。。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 103ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：103ms

var password:array[0..2001] of string;

g:array[0..2001] of longint;

i,j,k,n,max,len:integer;

re:string;

function check(s,ss:string):boolean;

begin

check:=false;

if pos(s,ss)=1 then check:=true;

end;

begin

readln(n);

for i:=1 to n do readln(password[i]);

for i:=n downto 2 do

for j:=i-1 downto 1 do

if check(password[j],password[i]) then inc(g[i]);

max:=0;

for i:=1 to n do if g[i]>max then max:=g[i];

writeln(max);

end.

很暴力地做的。。

program P1028;

var a:Array[1..2000] of string;

n,i,s,j,ans:longint;

str:string;

begin

readln(n);

for i:=1 to n do readln(a[i]);

for i:=1 to n do begin

s:=0;

for j:=1 to n do if length(a[i])>=length(a[j]) then begin

str:=copy(a[i],1,length(a[j]));

if str=a[j] then s:=s+1;

end;

if ans

不用自己编算法判断前缀

直接用pos函数就行了

也能秒杀

program p1028;

var

f:array[0..3000]of longint;

str:array[0..3000]of string;

i,j,n,ans:longint;

function check(a,b:longint):boolean;

var

t:longint;

begin

t:=pos(str[a],str);

if t=1 then exit(true) else exit(false);

end;

begin

readln(n);

for i:=1 to n do

begin

readln(str[i]);

f[i]:=1;

end;

for i:=1 to n do

for j:=1 to i-1 do

if check(j,i) then if f[j]+1>f[i] then f[i]:=f[j]+1;

for i:=1 to n do

if f[i]>ans then ans:=f[i];

writeln(ans);

end.

program vijos1028;

var i,j,n,max:integer;

h:array[1..2000] of integer;

a:Array[1..2000] of string;

function spd(a,b:string):boolean;

var i,lgs:integer;

begin

i:=1;

lgs:=length(b);

if lgs>=length(a) then

begin

while a[i]=b[i] do inc(i);

if i>length(a) then spd:=true else spd:=false

end

else spd:=false

end;

begin

max:=1;

readln(n);

for i:=1 to n do

begin

readln(a[i]);

h[i]:=1;

end;

for i:=2 to n do

for j:=1 to i-1 do

if spd(a[j],a[i]) then if h[j]max then max:=h[i];

{writeln(h[i]); }

end;

writeln(max);

readln

end.

我来提供一种判断前缀子串的方法！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

dp秒杀 用f[i]表示必须以第i个单词结尾的最长词数；

Trie 树

秒杀

program lf;

{$R-,Q-,S-}

var

s:array[0..2000] of string;

f,len:array[0..2000] of longint;

n:longint;

procedure init;

var

i:longint;

begin

readln(n);

for i:=1 to n do

begin

readln(s[i]);

len[i]:=length(s[i]);

end;

end;

procedure solve;

var

i,j,ans:longint;

begin

for i:=1 to n do

f[i]:=1;

for i:=2 to n do

for j:=1 to i-1 do

if copy(s[i],1,len[j])=s[j] then

if f[j]+1>f[i] then

f[i]:=f[j]+1;

ans:=0;

for i:=1 to n do

if f[i]>ans then ans:=f[i];

writeln(ans);

end;

begin

init;

solve;

end.