校内OJ 1128 词链(link)（Trie+DFS）-白红宇

校内OJ 1128 词链(link)（Trie+DFS）

阅读量：5091 次

发布时间：2019-06-13

本文共 1408 字，大约阅读时间需要 4 分钟。

1128: 词链(link)

时间限制: 1 Sec

内存限制: 64 MB

提交: 23

解决: 7

[ ][ ][ ]

题目描述

给定一个仅包含小写字母的英文单词表，其中每个单词最多包含50个字母。

如果一张由一个词或多个词组成的表中，每个单词（除了最后一个）都是排在它后面的单词的前缀，则称此表为一个词链。例如下面的单词组成了上个词链：

int

integer

而下面的单词不组成词链：

integer

intern

请在给定的单词表中取出一些词，组成最长的词链。最长的词链就是包含单词数最多的词链。

数据保证给定的单词表中，单词互不相同。

输入

第1行一个整数(n≤10000)，表示单词表中单词数；

接下来n行，每行一个单词。

输出

一个整数，表示最长词链长度。

样例输入

5iintegerinternetinternint

样例输出

本以为用字典树会很麻烦，结果还是挺好写的

用Trie之后DFS一下就行了

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  using namespace std;#define INF 0x3f3f3f3f#define CLR(x,y) memset(x,y,sizeof(x))#define LC(x) (x<<1)#define RC(x) ((x<<1)+1)#define MID(x,y) ((x+y)>>1)typedef pair
                   
                     pii;typedef long long LL;const double PI=acos(-1.0);const int maxl=55;const int maxn=26;struct Trie{ Trie *nxt[maxn]; int cnt; Trie() { cnt=0; for (int i=0; i
                    
                     nxt[indx]) { Trie *one=new Trie(); cur->nxt[indx]=one; cur=one; } else cur=cur->nxt[indx]; } ++(cur->cnt);}void dfs(Trie *now,int sum){ if(sum>ans) ans=sum; for (int i=0; i
                     
                      nxt[i]!=NULL) dfs(now->nxt[i],sum+now->nxt[i]->cnt);}int main(void){ L=new Trie(); int n; scanf("%d",&n); while (n--) { scanf("%s",s); update(s); } ans=0; dfs(L,0); printf("%d\n",ans); return 0;}