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)


相关推荐

  • linux convert 添加文字,Linux convert命令有什么用

    linux convert 添加文字,Linux convert命令有什么用Linuxconvert命令有什么用?Linux强大的图片处理功能强大的convert命令—介绍他的主要原因也是应为编程语言在linux下都可以调用使用convent命令可以对图片进行各种处理-trim:裁剪图像四周空白区域;-transparentcolor:去除图像中指定的颜色;-densitygeometry:设定图像的DPI值,若不明DPI值的概念,可参考《有关pt,p…

  • java类加载常见的几种问题理解类加载机制

    java类加载常见的几种问题理解类加载机制类加载过程中的相关概念详见-http://m.myexception.cn/program/1602930.html理解类加载过程的5步。Round1:首先请理解如下代码:classX{Yy=newY();publicX(){System.out.print(“X”);}}classY{publicY(){

  • JavaScript详细解析

    JavaScript详细解析文章目录1、JavaScript详细解析1.1、JavaScript介绍1.2、快速入门引入js的方式一:内部方式引入js的方式一:外部方式1.3、开发环境搭建1.4、快速入门总结2、JavaScript基本语法2.1、注释2.2、输入输出语句2.3、变量和常量2.4、原始数据类型和typeof方法2.4.1、原始数据类型2.4.2、typeof2.5、运算符2.6、流程控制和循环语句2.7、数组2.8、函数2.9、小结3、JavaScriptDOM3.1、DOM介绍3.2、Element元素的获取操作3

  • [Network]Wireless and Mobile

    [Network]Wireless and Mobile

  • 高级I/O函数之sendfile函数[通俗易懂]

    高级I/O函数之sendfile函数[通俗易懂]sendfile函数在两个文件描述符之间传递数据(完全在内核中操作),从而避免了内核缓冲区和用户缓冲区之间的数据拷贝,效率很高,被称为零拷贝。函数定义为:#include&lt;sys/sendfile.h&gt;ssize_tsenfile(intout_fd,intin_fd,off_t*offset,size_tcount);in_fd参数是待读出内容的文件描述符,out…

  • 网页title图标_php 数据库显示在页面并能修改

    网页title图标_php 数据库显示在页面并能修改在生成的pdf文件的页眉设置logo有以下解决方案重新定义TCPDF中的K_PATH_IMAGES常量(define(‘K_PATH_IMAGES’,xxxx),需要定义在加载tcpdf.php之前)##示例$logo=”xxxx”;//相对地址$pdf->SetHeaderData(PDF_HEADER_LOGO,PDF_HEADER_LOGO_WIDTH,”标题”,…

发表回复

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

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