聪明的Wangy给笨蛋的你玩字符串消消乐

给你一个下标从 0 开始的数组 words ，它包含 n 个字符串。

定义 连接 操作 join(x, y) 表示将字符串 x 和 y 连在一起，得到 xy 。如果 x 的最后一个字符与 y 的第一个字符相等，连接后两个字符中的一个会被 删除 （不会发生连锁反应，比如"aa"和"aa"连接得到"aaa"）。

比方说 join("ab", "ba") = "aba" ， join("ab", "cde") = "abcde" 。

聪明的Wangy让笨蛋的你执行 n - 1 次 连接 操作。令 str[0] = words[0] ，从 i = 1 直到 i = n - 1 ，对于第 i 个操作，你可以执行以下操作之一：

• 令 str[i]= join(str[i-1], words[i])
  

• 令 str[i] = join(words[i], str[i-1])
  

你的任务是使 str[n - 1] 的长度 最小 。

第一行输入一个整数n （1<=n<=1000）
接下来n行，每行代表字符串words[i]
1 <= words[i].length <= 50
words[i] 中只包含小写英文字母。

输出str[n-1]的最小长度

这个例子中，我们按以下顺序执行连接操作，得到 str2 的最小长度：
str0 = "aa"
str1 = join(str0, "ab") = "aab"
str2 = join(str1, "bc") = "aabc" 
str2 的最小长度为 4 。

2022级ACM集训队选拔赛（5）