luogu P1481 魔族密码
analysis
表示不想再写DP了,用trie树干掉
建好trie树,dfs求一下树中的每一条链上最多的标记数res便是结果了
code
#include<bits/stdc++.h>
using namespace std;
#define loop(i,start,end) for(register int i=start;i<=end;++i)
#define anri_loop(i,start,end) for(register int i=start;i>=end;--i)
#define clean(arry,num) memset(arry,num,sizeof(arry))
#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a<b)?a:b)
#define cacid(a) (a-'a')
int n,cnt=0,res=0;
const int maxn=2000+10;
int tree[75*maxn][26];
bool flag[75*maxn];
template<class T>void read(T &x)
{
x=0;char r=getchar();T neg=1;
while(r>'9'||r<'0'){if(r=='-')neg=-1;r=getchar();}
while(r>='0'&&r<='9'){x=(x<<3)+(x<<1)+r-'0';r=getchar();}
x*=neg;
}
void insert(char *s)
{
register int len=strlen(s);
int root=0;
loop(i,0,len-1)
{
int id=cacid(s[i]);
if(tree[root][id]==0)
{
tree[root][id]=++cnt;
flag[cnt]=false;
loop(i,0,25)tree[tree[root][id]][i]=0;
}
root=tree[root][id];
}
flag[root]=true;
}
void dfs(int pos,int cnt)
{
res=max(res,cnt);
loop(i,0,25)
{
if(tree[pos][i]!=0)dfs(tree[pos][i],cnt+((flag[tree[pos][i]])?1:0));
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("datain.txt","r",stdin);
#endif
read(n);
clean(flag,false);
clean(tree,0);
char _s[100];
loop(i,1,n)
{
scanf("%s",_s);
insert(_s);
}
dfs(0,0);
printf("%d",res);
return 0;
}