Problem Statement
本题只出现大写字母。
定义字符串的重量为对于所有出现了的字母,将其最后一次出现的位置-第一次出现的位置加起来得到的数。
定义一个字符串是轻的,当且仅当它是所有同长度的字符串里重量最小的之一。
现在你需要选择n个轻的字符串,将它们顺次相接,第i个字符串的长度是L[i],
问最后得到的字符串的重量最少是多少。
1 <= n <= 50;1 <= L[i] <= 100.
In this problem, all strings consist of uppercase English letters only.
That is, there are 26 distinct letters.
The weight of a string S can be computed as follows:
for each letter that occurs at least once in S, its leftmost and rightmost occurrences L and R are found and the weight is increased by R-L.
For example, if S="ABCACAZ", the weight of S is (5-0) + (1-1) + (4-2) + (6-6) = 7.
(The leftmost occurrence of 'A' is at the index L=0, the rightmost one is at R=5, so 'A' contributes 5-0 = 5 to the weight of S. The only 'B' contributes 0, the pair of 'C's adds 2, and the only 'Z' adds 0.)
A string is S called light if no other string of the same length has a smaller weight.
You are given a int[] L.
Manao is going to choose some light strings.
The elements of L specify the lengths of these strings.
For example, if L = { 3, 42, 1 }, Manao will first choose a light string of length 3, then a light string of length 42, and finally a light string of length 1.
Then, Manao is going to concatenate all of the chosen strings, in the given order.
Compute and return the smallest possible weight of a string Manao may obtain at the end.