Problem
Some time ago, Dejan Stojanovic, a Serbian poet, said: “Words rich in meaning can be cheap in sound
effects.” Is it true? A String Processing professor at UFPE wants to test this quote with strings. For that, he defined what he calls a “cheap B-subsequence”. A cheap B-subsequence, according to his definition, is a subsequence of size B, of a string S(B <= |S|), that has the lowest associated cost. To define the cost of a string, the professor determined a series of rules to each letter of the alphabet. The alphabet that he used contains only lowercase letters. The rule of a letter is defined as a set of pairs (Pi, Ci), which indicates that if this letter appears in a position X on the subsequence, where X is a multiple of Pi, then the cost of (X/Pi) * Ci will be added to the total cost of this subsequence. Let’s show an example. Suppose we have the following rules:
Suppose we have the string abaabcbc
, and B = 4. If we choose the subsequence aabc
(abaabcbc), we would do the following procedure to calculate the associated cost:
The first letter of the sequence is an
a
, and the position 1 is neither multiple of 2 or 4, so the cost is0
;The second letter of the sequence is another
a
, and the position 2 is a multiple of 2, so we’ll add the cost of(2/2) * 3 = 3
;- The third letter of the sequence is a
b
, and the position 3 is multiple of 1, so we will add the cost of(3/1) * 4 = 12
; - The last letter of the sequence is a
c
, and the position 4 is a multiple of 1 and 4, so we will add
the cost of(4/1) * 2 + (4/4)* 20 = 28
.
The total associated cost to this subsequence is 43, which is not the lowest cost, since we could have chosen aaab (abaabcbc) and obtained an associated cost of 19 | this is indeed the cost of the cheap B-subsequence. Given the string S and the integer B, and the rules of the alphabet, your task is to create a program that tells the professor the cost of the cheap B-subsequence.
Input
The first line contains T (T < 100)- the number of test cases, after this line T test cases follows. The first line of a test case contains a string S of lowercase letters and an integer B
(1 <= B <= |S| <= 100). Each of the next 26 lines describe the rule of each letter. The first of the 26 lines corresponds to the rule of the letter a
; the following line corresponds to the rule of the letter b
; the last of the 26 lines corresponds to the rule of the letter z
. Each line containing a rule is described in the following way:
Q, P1, C1, P2, C2, … PQ, CQ
(1 <= Q <= 10; 1 <= Pi <= |S|; 1 <= Ci <= 50), where Q is the amount of pairs associated to this rule, and is followed by the pairs themselves.
Output
For each test case print a line containing Case #X: Y
, where X is the case number, starting at 1, and Y is the cost of the cheap B-subsequence.
Sample Input
|
|
Sample Output
|
|
Solution
題目描述:
找一個長度為 B
的 subsequence,並且每一個字符成本如題目所定義,求最小構成成本。
題目解法:
動態規劃,狀態 dp[length][subsequence_index]
|
|