#P5657. [BJWC2018] 词韵

    ID: 4658 传统题 1500ms 512MiB 尝试: 3 已通过: 1 难度: 7 上传者: 标签>难度分类提高+/省选-字符串Trie动态规划树形 DP数据结构链表CF2200

[BJWC2018] 词韵

题目描述

Adrian 很喜欢诗歌中的韵。记 L(A,B)L(A,B) 为单词 AA 与 BB 的最长公共后缀长度。当且仅当

L(A,B)≥max⁡(∣A∣,∣B∣)−1L(A,B)\ge \max(|A|,|B|)-1

时,两个单词押韵。

给定 NN 个互不相同的单词,可以从中选取若干个单词并任意排列,每个单词最多选一次。要求序列中任意两个相邻单词都押韵,求序列的最大长度。

输入格式

第一行是一个整数 NN。

接下来NN 行,每行一个由小写英文字母组成的字符串,表示每个单词。所有单词互不相同。

输出格式

输出一行,为一个整数,表示最长单词序列的长度。

样例 #1

5
ask
psk
k
krafna
sk
4

提示

【样例解释】

一种最长单词序列是 ask、psk、sk、k。

【数据规模和约定】

  • 对于 30%30\% 的数据,1≤N≤201\le N\le 20,所有单词长度之和不超过 30003000。
  • 对于所有数据,1≤N≤5×1051\le N\le 5\times 10^5,所有单词长度之和不超过 3×1063\times 10^6。