Optimal Keypad[通俗易懂]

Optimal Keypad[通俗易懂]Description OptimusMobilesproducesmobilephonesthatsupportSMSmessages.TheMobileshaveakeypadof12keys,numbered1to12.Thereisacharacterstringassignedtoeachkey.Totypeinthe

大家好,又见面了,我是你们的朋友全栈君。

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[通俗易懂]
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[通俗易懂]

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");	}	} 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/130633.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • CCF201503试题

    CCF201503试题

  • sublime Text3配置及快捷键、插件推荐总结

    sublime Text3配置及快捷键、插件推荐总结

    2021年11月29日
  • matlab画三维图像函数_matlab怎么画图像

    matlab画三维图像函数_matlab怎么画图像PAT甲级1001&period;A&plus;BFormat&lpar;20&rpar;题目原文:Calculatea+bandoutputthesuminstandardformat–thatis,thedigitsmustbeseparated…ASP&period;NETCore管道深度剖析(3…

    2022年10月10日
  • java script 下载_JavaScript下载[通俗易懂]

    java script 下载_JavaScript下载[通俗易懂]JavascriptPlus是一个小巧的Javascript脚本辅助编程工具,主要方便开发者对js代码进行测试、预览以及运行等操作,特点包括用不同的颜色显示语法和关键词,有稍许的程序输入预测功能,测试运行子程序等等。JavascriptPlus是一款功能强劲的javascript文本编辑器。内置的智能系统能够提示你-各种Javascript物件、性质和触发事件,-各种Html和Shee…

  • java数据库连接池有哪些_常用的数据库连接池

    java数据库连接池有哪些_常用的数据库连接池池(Pool)技术在一定程度上可以明显优化服务器应用程序的性能,提高程序执行效率和降低系统资源开销。这里所说的池是一种广义上的池,比如数据库连接池、线程池、内存池、对象池等。其中,对象池可以看成保存对象的容器,在进程初始化时创建一定数量的对象。需要时直接从池中取出一个空闲对象,用完后并不直接释放掉对象,而是再放到对象池中以方便下一次对象请求可以直接复用。其他几种池的设计思想也是如此,池技术的优势是…

  • 流程引擎BPM对比[通俗易懂]

    流程引擎BPM对比[通俗易懂]流程引擎就是“业务过程的部分或整体在计算机应用环境下的自动化”,它主要解决的是“使在多个参与者之间按照某种预定义的规则传递文档、信息或任务的过程自动进行,从而实现某个预期的业务目标,或者促使此目标的实现”。通俗的说,流程就是多种业务对象在一起合作完成某件事情的步骤,把步骤变成计算机能理解的形式就是流程引擎。

    2022年10月20日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号