首页 > ACM题库 > HDU-杭电 > hdu 2666 Language-待解决-[解题报告]C++
2014
02-12

hdu 2666 Language-待解决-[解题报告]C++

Language

问题描述 :

Alphabet Ak consists of k initial letters of English alphabet. A positive integer called a weight is assigned to each letter of the alphabet. A weight of a word built from the letters of the alphabet Ak is the sum of weights of all letters in this word. A language over an alphabet Ak is any finite set of words built from the letters of this alphabet. A weight of a language is the sum of weights of all its words. We say that the language is prefixless if for each pair of different words w, v from this language w is not a prefix of v.We want to find out what is the minimal possible weight of an n-element, prefixless language over an alphabet Ak.

Example
Assume that k = 2 , the weight of the letter a – W(a)=2 and the weight of the letter b – W(b) = 5. The weight of the word ab – W(ab)= 2+5=7. W(aba)=2+5+2=9. The weight of the language J = {ab, aba, b} – W(J) = 21. The language J is not prefixless, since the word ab is a prefix of aba. The lightest tree-element, prefixless language over the alphabet A2 (assuming that weights of the letters are as before) is {b, aa, ab}; its weight is 16.

Task
Write a program that:
1.reads two integers n, k and the weights of k letters of an alphabet Ak;
2.computes the minimal weight of a prefixless, n-element language over the alphabet Ak;

输入:

The first line is the number of test cases.
For each test cast, there are two positive integers n and k separated by a single space, (2<=n<=10000, 2<=k<=26). These are the number of words in a language and the number of letters in an alphabet respectively. The second line contains k positive integers separated by single spaces. Each of them is not greater than 10000. The i-th number is the weight of the i-th letter.

输出:

The first line is the number of test cases.
For each test cast, there are two positive integers n and k separated by a single space, (2<=n<=10000, 2<=k<=26). These are the number of words in a language and the number of letters in an alphabet respectively. The second line contains k positive integers separated by single spaces. Each of them is not greater than 10000. The i-th number is the weight of the i-th letter.

样例输入:

1 
3 2 
2 5

样例输出:

16

 


  1. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks