#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
char word[2010][10000];
int lian[2010]={0},maxn=0;
int main() {
int n;
cin >> n;
for (int i=1; i<=n; i++) {
scanf("%s",word[i]);
lian[i]=1;
}
for (int i=2; i<=n; i++) {
for (int j=i-1; j>=1; j--) {
int flag=1;
for (int t=0; t<10000; t++) {
if (word[j][t]=='\0') break;
if (word[i][t]=='\0') { flag=0; break;}
if (word[j][t]!=word[i][t]) { flag=0; break;}
}
if (flag) {
lian[i]=lian[j]+1;
break;
}
}
if (lian[i]>maxn) maxn=lian[i];
}
cout << maxn;
return 0;
}

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int n;
int sum;
struct yu
{
string m;
int len;
}yu[2005];
void yux(int x,int y)
{
if(sum<y)sum=y;
if(n-x+y<sum)return ;

for(int i=x+1;i<n;i++)
{
if(yu[i].m.substr(0,yu[x].len)==yu[x].m){yux(i,y+1);}
}
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
cin>>yu[i].m;
yu[i].len=yu[i].m.length();
}
for(int i=0;i<n;i++){
if(n-i+1<sum){}
else yux(i,1);
}
printf("%d",sum);
return 0;
}

/*

author: Slience_K
Belong: C++
Pro: Vijos P 1068

*/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n , f[ 2005 ] , ans;
char s[ 2005 ][ 1005 ];
bool Front( int x , int y ){
int lenx , leny;
lenx = strlen( s[ x ] );
leny = strlen( s[ y ] );
if ( lenx > leny ) return 0;
for( int i = 0 ; i < lenx ; i++ )
if ( s[ x ][ i ] != s[ y ][ i ] ) return 0;
return 1;
}
int main(){
freopen( "P1028.in" , "r" , stdin );
scanf( "%d" ,&n );
for( int i = 1 ; i <= n ; i++ )
scanf( "%s" , s[ i ] );
f[ 1 ] = 1;
for( int i = 2 ; i <= n ; i++ ){
for( int j = 1 ; j <= i - 1 ; j++ )
if ( Front( j , i ) ) f[ i ] = max( f[ i ] , f[ j ] + 1 );
if ( !f[ i ] ) f[ i ] = 1; //这一句不可少。。。
}

ans = 1;
for( int i = 1 ; i <= n ; i++ )
ans = max( ans , f[ i ] );
printf( "%d" , ans );
return 0;
}

Trie求解
#include <cstdio>
#include <cstring>
#include <algorithm>
const int maxn=2000;
const int maxLength=75;
struct pointerList;
struct trieNode;
struct pointerList
{
trieNode* node;
pointerList* next;
pointerList()
{
node=NULL;
next=NULL;
}
};
struct trieNode
{
pointerList* childList;
char key;
int count;
trieNode(char k=' ')
{
key=k;
count=0;
childList=NULL;
}
};
int N;char word[maxn+5][maxLength+5];
trieNode* root;
int search(int wordIdx,int length,trieNode* root,int cur=0,int count=0)
{
root->count=count;
if(cur==length) return count;
if(!root->childList)
{
root->childList=new pointerList();
root->childList->node=new trieNode(word[wordIdx][cur]);
int ct;ct=(cur==length-1?root->count+1:root->count);
return search(wordIdx,length,root->childList->node,cur+1,ct);
}
else
{
pointerList* &curPos=root->childList;//这里最初没设为引用导致wa一次
bool found=false;
while(curPos)
{
if(word[wordIdx][cur]==curPos->node->key)
{
found=true;
return search(wordIdx,length,curPos->node,cur+1,
cur==length-1?curPos->node->count+1:curPos->node->count);
break;
}
else curPos=curPos->next;
}
if(!found)
{
curPos=new pointerList();
curPos->node=new trieNode(word[wordIdx][cur]);
int ct;ct=(cur==length-1?root->count+1:root->count);
return search(wordIdx,length,curPos->node,cur+1,ct);
}
}
}
int main()
{
scanf("%d",&N);
for(int i=0;i<N;i++) scanf("%s",word[i]);
root=new trieNode();
int ans=0;
for(int i=0;i<N;i++)
ans=std::max(ans,search(i,strlen(word[i]),root));
printf("%d",ans);
return 0;
}

没有初始化d[i]=1和判断d[i]和d[j]的大小关系害我wa了一次，AC70题纪念～(￣▽￣～)~
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

const int maxn=2000+5;
int d[maxn]={0},n,ans=1;
string s[maxn];

int main() {
ios::sync_with_stdio(0);
cin>>n;
for (int i=1;i<=n;++i) {
cin>>s[i];
d[i]=1;
for (int j=1;j<i;++j) {
if (s[i].size()>s[j].size()&&s[i].substr(0,s[j].size())==s[j])
d[i]=max(d[i],d[j]+1);
}
if (d[i]>ans) ans=d[i];
}
cout<<ans;
}

本题可以视作最长上升子序列的变种，只不过把前一项小于后一项改作前一项是后一项的前缀。
有人说用栈做可以O(n)，我不清楚原因，希望大神指教。

####程序
program password;
type strin=string[75];
var
a:array[1..2000] of strin;
f:array[1..2000] of integer;
i,j,n,max:integer;
function check(x,y:strin):boolean;
begin
if pos(x,y)=1 then exit(true) else exit(false);
end;
begin
readln(n);
for i:=1 to n do f[i]:=1;
for i:=1 to n do readln(a[i]);
for i:=n-1 downto 1 do
for j:=i+1 to n do
if check(a[i],a[j]) then
if f[j]+1>f[i] then f[i]:=f[j]+1;
max:=0;
for i:=1 to n do if f[i]>max then max:=f[i];
writeln(max);
readln;
end.

uses math;
var n,i,j,max:longint;
data:array[1..2000] of ansistring;
num:array[1..2000] of longint;
begin
readln(n);
for i:=1 to n do num[i]:=1;
for i:=1 to n do readln(data[i]);
for i:=1 to n do
for j:=1 to n do
if (i<>j) and (length(data[i])>length(data[j])) then
if copy(data[i],1,length(data[j]))=copy(data[j],1,length(data[j])) then
num[i]:=1+num[j];
max:=maxvalue(num);
write(max);
end.

字典树也很简单。把C++当java用吧，不需要回收内存。
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
struct Node{
Node(){
memset(son, 0, sizeof(son));
isword = false;
}
Node* son[26];
bool isword;
};
int size;
Node* root;
void insert(char word[]){
int i;
Node* now = root;
for (i = 0; word[i]; i++){
if (now->son[word[i] - 'a']==0)
now->son[word[i] - 'a'] = new Node();
now = now->son[word[i] - 'a'];

}
now->isword = true;
}
int deep(Node* r){
int i;
int ans = 0;
for (i = 0; i < 26; i++){
if (r->son[i]){
int sondeep = deep(r->son[i]);
if (sondeep>ans)ans = sondeep;
}
}
if (r->isword){
ans++;
}
return ans;
}
int main(){
freopen("in.txt", "r", stdin);
root = new Node();
cin >> size;
int i;
char word[77];
for (i = 0; i < size; i++){
cin >> word;
insert(word);
}
cout << deep(root) << endl;
return 0;
}

写那么长的什么心态？？？明显的动规更简单，这题不适合用字典树去dps。

纪念第一次自己看出动规同时一遍AC

###blcok code
program P1028;
uses math;
var n,i,j,max:longint;
data:array[1..2000] of ansistring;
num:array[1..2000] of longint;
begin
readln(n);
for i:=1 to n do num[i]:=1;
for i:=1 to n do readln(data[i]);
for i:=1 to n do
for j:=1 to n do
if (i<>j) and (length(data[i])>length(data[j])) then
if copy(data[i],1,length(data[j]))=copy(data[j],1,length(data[j])) then
num[i]:=1+num[j];

max:=maxvalue(num); //测试下math库里求数组里最大值的函数，不知道这个效率怎么样，如果效率低还得用堆之类的数据结构啊~
write(max);
end.

#include<stdio.h>
#include<string.h>
#define max1 5050
#define max2 100
char a[max1][max2];
int main()
{
int m,k,i,c[10000],max3=0;
scanf("%d",&m);
for(i=1;i<=m;i++)
{
scanf("%s",a[i]);
getchar();
}
for(i=1;i<=m;i++)
{
c[i]=1;
for(k=1;k<i;k++)
{
if(strnicmp(a[i],a[k],strlen(a[k]))==0&&strlen(a[i])>strlen(a[k])&&c[i]<c[k]+1)
c[i]=c[k]+1;
}
if(max3<c[i])
max3=c[i];
}
printf("%d",max3);
}

program _1028mozu;
type trie=^node;
node=record
data:longint;
list:array[1..26]of trie;// 数字array[0..9]of trie
end;
var head,p,q:trie;
n,i,j,count,maxx:longint;
s:ansistring;
function max(a,b:longint):longint;
begin
if a>b then exit(a)
else exit(b);
end;

procedure ini(x:trie);
var ii:longint;
begin
x^.data:=0;
for ii:=1 to 26 do
x^.list[ii]:=nil;
end;

function turn(a:char):longint;// 由字母转为数字（第几个字母）
begin
turn:=ord(a)-ord('a')+1;
end;

procedure TrieTree;
begin
new(head);// 建立头指针
ini(head);
for i:=1 to n do// 建立字典
begin
readln(s);
new(p);
p:=head;
for j:=1 to length(s) do
begin
if p^.list[turn(s[j])]=nil then// 如果结点为空，则新建一结点
begin
new(q);
p^.list[turn(s[j])]:=q;
ini(q);
p:=q;
end
else p:=p^.list[turn(s[j])];
end;
inc(p^.data);// 在单词的末字母处标记
end;
end;

procedure dfs(temp:trie);
var i:longint;
begin
for i:=1 to 26 do
if temp^.list[i]<>nil then
begin
if temp^.list[i]^.data<>0 then
begin
inc(count,temp^.list[i]^.data);
maxx:=max(maxx,count);
dfs(temp^.list[i]);
dec(count,temp^.list[i]^.data);
end
else dfs(temp^.list[i]);
end;
end;

begin
readln(n);
TrieTree;
maxx:=0;count:=0;
dfs(head);
writeln(maxx);
end.
字典树+深搜 program _1028mozu;
type trie=^node;
node=record
data:longint;
list:array[1..26]of trie;// 数字array[0..9]of trie
end;
var head,p,q:trie;
n,i,j,count,maxx:longint;
s:ansistring;
function max(a,b:longint):longint;
begin
if a>b then exit(a)
else exit(b);
end;

procedure ini(x:trie);
var ii:longint;
begin
x^.data:=0;
for ii:=1 to 26 do
x^.list[ii]:=nil;
end;

function turn(a:char):longint;// 由字母转为数字（第几个字母）
begin
turn:=ord(a)-ord('a')+1;
end;

procedure TrieTree;
begin
new(head);// 建立头指针
ini(head);
for i:=1 to n do// 建立字典
begin
readln(s);
new(p);
p:=head;
for j:=1 to length(s) do
begin
if p^.list[turn(s[j])]=nil then// 如果结点为空，则新建一结点
begin
new(q);
p^.list[turn(s[j])]:=q;
ini(q);
p:=q;
end
else p:=p^.list[turn(s[j])];
end;
inc(p^.data);// 在单词的末字母处标记
end;
end;

procedure dfs(temp:trie);
var i:longint;
begin
for i:=1 to 26 do
if temp^.list[i]<>nil then
begin
if temp^.list[i]^.data<>0 then
begin
inc(count,temp^.list[i]^.data);
maxx:=max(maxx,count);
dfs(temp^.list[i]);
dec(count,temp^.list[i]^.data);
end
else dfs(temp^.list[i]);
end;
end;

begin
readln(n);
TrieTree;
maxx:=0;count:=0;
dfs(head);
writeln(maxx);
end.
字典树+深搜program _1028mozu;
type trie=^node;
node=record
data:longint;
list:array[1..26]of trie;// 数字array[0..9]of trie
end;
var head,p,q:trie;
n,i,j,count,maxx:longint;
s:ansistring;
function max(a,b:longint):longint;
begin
if a>b then exit(a)
else exit(b);
end;

procedure ini(x:trie);
var ii:longint;
begin
x^.data:=0;
for ii:=1 to 26 do
x^.list[ii]:=nil;
end;

function turn(a:char):longint;// 由字母转为数字（第几个字母）
begin
turn:=ord(a)-ord('a')+1;
end;

procedure TrieTree;
begin
new(head);// 建立头指针
ini(head);
for i:=1 to n do// 建立字典
begin
readln(s);
new(p);
p:=head;
for j:=1 to length(s) do
begin
if p^.list[turn(s[j])]=nil then// 如果结点为空，则新建一结点
begin
new(q);
p^.list[turn(s[j])]:=q;
ini(q);
p:=q;
end
else p:=p^.list[turn(s[j])];
end;
inc(p^.data);// 在单词的末字母处标记
end;
end;

procedure dfs(temp:trie);
var i:longint;
begin
for i:=1 to 26 do
if temp^.list[i]<>nil then
begin
if temp^.list[i]^.data<>0 then
begin
inc(count,temp^.list[i]^.data);
maxx:=max(maxx,count);
dfs(temp^.list[i]);
dec(count,temp^.list[i]^.data);
end
else dfs(temp^.list[i]);
end;
end;

begin
readln(n);
TrieTree;
maxx:=0;count:=0;
dfs(head);
writeln(maxx);
end.
字典树+深搜

指针写的标准的字典树，插入的时候判断路径上有几个完整的单词，加一后输出。
#include<cstdio>
#include<cstring>

struct Trienode
{
bool is_end;
Trienode *next[26];
Trienode()
{
is_end=0;
memset(next,0,sizeof(next));
}
}*root;

int N,ans=1;
char str[76];

inline int max(int a,int b)
{
return a>b?a:b;
}

void insert(char str[])
{
Trienode *now=root;
int count=1;
for(int i=0,len=strlen(str);i<len;i++)
if (now->next[str[i]-97])
{
now=now->next[str[i]-97];
if (now->is_end) count++;
}
else
{
now->next[str[i]-97]=new Trienode;
now=now->next[str[i]-97];
}
now->is_end=1;
ans=max(ans,count);
}

int main()
{
scanf("%d\n",&N);
root=new Trienode;
for(int i=0;i<N;i++)
insert(gets(str));
printf("%d",ans);
return 0;
}

trie+dfs

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;

struct Trie{
int ch[10000][26];
int val[10000];
int sz,ans;
Trie(){
ans=-1;sz=1;memset(val,0,sizeof(val));
}
int idx(char c){return c-'a';}

void insert(char *s){
int u=0,n=strlen(s);
for(int i=0;i<n;i++){
int c=idx(s[i]);
if(!ch[u][c]){
memset(ch[sz],0,sizeof(ch[sz]));
val[sz]=0;
ch[u][c]=sz++;
}
u=ch[u][c];
}
val[u]=1;
}

void dfs(int u,int cur){
for(int i=0;i<26;i++)
if(ch[u][i]){
if(val[u])
dfs(ch[u][i],cur+1);
else dfs(ch[u][i],cur);
}
if(val[u]) cur++;
if(cur>ans) ans=cur;
}
}trie;

int main(){
int n;
char s[80];
cin>>n;
for(int i=0;i<n;i++){
cin>>s;
trie.insert(s);
}
trie.dfs(0,0);
cout<<trie.ans<<endl;

return 0;
}

数组开上千的都是什么心态啊……话说我这算是DP吗？自己也不知道啦- -。
program a01;
var
n,i,ans,head:longint;
c:char;
mark:boolean;
a:array[1..100] of char;
b:array[1..100] of longint;
begin
readln(n);
for i := 1 to n do
begin
head:=0;
mark:=false;
while not eoln do
begin
read(c);
inc(head);
if a[head]<>c then begin
a[head]:=c;
b[head]:=b[head-1];
mark:=true;
break;
end;
end;
if mark then while not eoln do
begin
read(c);
inc(head);
a[head]:=c;
b[head]:=b[head-1];
end;
b[head]:=b[head-1]+1;
if b[head]>ans then ans:=b[head];
readln;
end;
writeln(ans);
end.
测试数据 #0: Accepted, time = 0 ms, mem = 820 KiB, score = 10

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

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

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

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

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

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

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

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

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

Accepted, time = 0 ms, mem = 824 KiB, score = 100

nlogn藐视……

var
a,f:array[1..2000] of string;
ans,i,j,k,l,r,mid,n:longint;
begin
readln(n);
for i:=1 to n do
readln(a[i]);

for i:=1 to n do
begin
l:=1; r:=ans;
while l<=r do
begin
mid:=(l+r) shr 1;
if pos(f[mid],a[i])=1 then
l:=mid+1
else
r:=mid-1;
end;
f[l]:=a[i];
if l>ans then
ans:=l;
end;
writeln(ans);
end.

测试数据 #0: Accepted, time = 15 ms, mem = 372 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 368 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 368 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 372 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 368 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 372 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 372 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 376 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 368 KiB, score = 10
测试数据 #9: Accepted, time = 140 ms, mem = 368 KiB, score = 10
Accepted, time = 155 ms, mem = 376 KiB, score = 100

var
a:array[0..2001] of string;
x:array[0..2001] of longint;
b,c,d,e:longint;
begin
readln(b);
for c := 1 to b do readln(a[c]);
for c := 1 to b do x[c]:=1;
e:=0;
for c := 2 to b do
for d := 1 to c-1 do
if pos(a[d],a[c])=1 then
if x[d]>=x[c] then
begin
x[c]:=x[d]+1;
if x[c]>e then e:=x[c];
end;
write(e);
end.

水水水水水
动归秒过

var n,m,mm,i,j:longint;f:array[0..2000]of longint;
a:array[0..2000]of string[100];
function max(c,d:longint):longint;
begin
if c>d then exit(c)else exit(d);
end;
function pd(x,y:longint):boolean;
var k:longint;
begin
k:=pos(a[x],a[y]);
if k=1 then exit(true) else exit(false);
end;
begin
readln(n);fillchar(f,sizeof(0),0);f[1]:=1;
for i:=1 to n do readln(a[i]);
for i:=2 to n do
begin
m:=0;
for j:=1 to i-1 do if pd(j,i)then m:=max(f[j],m);
f[i]:=m+1;
end;
mm:=0;
for i:=1 to n do mm:=max(mm,f[i]);
writeln(mm);
end.

利用栈可以达到O(n)。
如果栈顶元素是它的前缀那么就把它入栈，如果不是则一直取出栈顶元素直到栈顶元素是其前缀为止。
因为输入数据按字典序排列，可以保证算法的正确性。

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