大家好，又见面了，我是你们的朋友全栈君。
Description
Optimus Mobiles produces mobile phones that support SMS messages. The Mobiles have a keypad of 12 keys, numbered 1 to 12. There is a character string assigned to each key. To type in the n-th character in the character string of a particular key, one should press the key n times. Optimus Mobiles wishes to solve the problem of assigning character strings to the keys such that for typing a random text out of a dictionary of common words, the average typing effort (i.e. the average number of keystrokes) is minimal.
![Optimal Keypad[通俗易懂]](http://qn.javajgs.com/20220428/de529af7-d27f-49d4-bf67-9be9614f612820220428868fd719-3f1c-49c4-9c79-6aa0d56bf0971.jpg)
![Optimal Keypad[通俗易懂]](https://javaforall.net/wp-content/uploads/2020/11/2020110817443450.jpg)
Figure 1
To be more precise, consider a set of characters {a, b, c,…, z, +, *, /, ?} printed on a label tape as in Fig. 2. We want to cut the tape into 12 pieces each containing one or more characters. The 12 labels are numbered 1 to 12 from left to right and will be assigned to the keypad keys in that order.
![Optimal Keypad[通俗易懂]](http://qn.javajgs.com/20220428/20cb52cb-3ff9-41dd-97ce-a9ef54747e4320220428216b01e7-6372-4735-9fae-dbae151241a41.jpg)
Figure 2
You are to write a program to find the 11 cutting positions for a given dictionary of common words. The cutting positions should minimize the average number of keystrokes over all common words in the dictionary. Your output should be a string of 11 characters, where character i in this string is the first character of the (i+1)
th label.
Input
The first line contains a single integer t (1 <= t <= 10), the number of test cases. Each test case starts with a line, containing an integer M (1 <= M <= 10000), the number of common words in the test case. In each M subsequent line, there is a common word. Each common word contains at most 30 characters from the alphabet {a, b, c,…, z, +, *, /, ?}.
Output
The output contains one line per test case containing an optimal cut string. Obviously, there may be more than a single optimal cut string, so print the optimal cut string which is the smallest one in lexicographic order.
Sample Input
2
2
hi
ok
5
hello
bye
how
when
who
Sample Output
bcdefghijko
bcdefhlnowy
Source
/**题目大意：给出“abcd...z+* /?"的序列，要求分为12段，作为手机的12个按键上的字符，使得我们用手机输入单词时按键的次数最少，单词的数量是10000每个长度最大为30。 思路：注意到输入的顺序可以打乱，即输入“ab”和输入“ba”花费是一样的，我们可以预处理一下，统计这30个字符出现的次数，现在我们要做的就是把这 30个字符分成12份。容易想到的方程是 dp[i][j] = min{ dp[i - 1][k - 1] + sum(k, j) }; dp[i][j]表示前j个字符分成i份，sum(k, j)表示第k个字符到第j个字符划分在同一个按键内的花费；最后记录一下路径。 **/ #include <iostream> #include <cstring> #include <cstdio> using namespace std;const int N = 32;char alph[] = " abcdefghijklmnopqrstuvwxyz+*/?";int flect[140];int num[N];int s[N][N];int dp[N][N];int ans[N];void init(){ for (int i = 1; i <= 30; i++) flect[(int) alph[i]] = i;} char str[N];int main(){ //freopen("in.txt", "r", stdin); init(); int n, T, i, j, k; scanf("%d", &T); while (T--) { scanf("%d", &n); memset(num, 0, sizeof(num)); for (i = 0; i < n; i++) { scanf("%s", str); for (j = 0; str[j]; j++) num[flect[(int)str[j]]]++; } //dp memset(dp, 0x3f, sizeof(dp)); int sum = 0; for (i = 1; i <= 19; i++) { sum += num[i] * i; dp[1][i] = sum; s[1][i] = 1; } for (i = 2; i <= 12; i++) for (j = i; j <= 30; j++) { for (k = i; k <= j; k++) { sum = 0; for (int h = k; h <= j; h++) sum += num[h] *(h - k + 1); if (dp[i - 1][k - 1] + sum < dp[i][j]) { dp[i][j] = dp[i - 1][k - 1] + sum; s[i][j] = k; } } } int cnt = 0; int now = 30; for (i = 12; i > 1; i--) { ans[cnt++] = s[i][now]; now = s[i][now] - 1; } for (i = cnt - 1; i >= 0; i--) printf("%c", alph[ans[i]]); printf("\n"); } } 发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/130633.html原文链接：https://javaforall.net
