back to the menu

Flag Counter TopCoder SRM 586 - 1000: StringWeight

SRM 586 1 1000 StringWeight


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.

Definition

(be sure your method is public)

Limits

Constraints

Test cases

  1. input
    • L { 1 }
    output
    Returns 0
    note
    Every string of length 1 has weight 0.
  2. input
    • L { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
    output
    Returns 1
    note
    Manao is going to concatenate 27 strings of length 1. If Manao takes 25 distinct strings and 2 equal strings and places the equal strings side by side, the weight of the resulting string will be 1.
  3. input
    • L { 26, 2, 2 }
    output
    Returns 8
    note
    One possible concatenation of minimum weight is "ABC...XYZ"+"YZ"+"YZ".
  4. input
    • L { 25, 25, 25, 25 }
    output
    Returns 1826
  5. input
    • L { 14, 6, 30, 2, 5, 61 }
    output
    Returns 1229

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.