Dotcpp  >  编程题库  >  蓝桥杯2024年第十五届省赛真题-前缀总分
题目 3245:

蓝桥杯2024年第十五届省赛真题-前缀总分

时间限制: 3s 内存限制: 512MB 提交: 111 解决: 18

题目描述

给定 n 个由小写英文字母组成的字符串 s1, s2, · · · , sn ,定义前缀总分为V =∑i<j P(si, sj) ,其中 P(si, sj) 表示 si, sj 的最长公共前缀的长度。

小蓝可以选择其中一个字符串,并修改其中的一个字符。请问修改后前缀总分最大为多少?

输入格式

输入的第一行包含一个正整数 n 。接下来 n 行,每行包含一个字符串 si 。

输出格式

输出一行包含一个整数表示答案。

样例输入

3
aab
bbb
abb

样例输出

5

提示

【样例说明】

将第二个字符串改为 abb ,得分为 P(aab, abb)+P(aab, abb)+P(abb, abb) =1 + 1 + 3 = 5 。

【评测用例规模与约定】

对于 20% 的评测用例,1 ≤ n ≤ 20 ;

对于所有评测用例,1 ≤ n ≤ 200 ,1 ≤ |si| ≤ 200 ,其中 |si| 表示 si 的长度。

标签