OI题库

【题目描述】

科学进步飞快，日新月异，人们早已经不再习惯十进制那种单调的表示数字的方式。最近，Y同学投入百进制数的研究中。两个百进制数可以相邻当且仅当前一个百进制数的最后一位和后一个百进制数的第一位相同，这一位数字称之为一个交点，每一位数字最多能以起点和终点的角色属于交点一次（例如1234—3434—3412，是非法序列，因为34以起点和终点的角色充当交点各两次）。任意一个百进制数或多个可以相邻的百进制数可以形成一个合法序列。一个完美序列满足序列中所有的百进制数长度之和是所有合法序列中最大的。给出n个百进制数，我们希望将其排列才能组成最长的百进制数完美序列。

【输入格式】

第一行一个数n表示百进制数的个数；

第二行到第n-1行每行一个长度为L的百进制数。

【输出格式】

输出完美序列的长度

【样例输入】

5 
1234 
347891 
1291 
9988 
9156 

【样例输出】

14

【提示】

20%的数据：1≤n≤10,1≤L≤10;

80%的数据：1≤n≤50,1≤L≤100;

100%的数据：1≤n≤100,1≤L≤100;

【来源】

在此键入。