首页 > 代码库 > HDU 1523 Decoding Morse Sequences
HDU 1523 Decoding Morse Sequences
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1523
此题大意为 给你一串摩尔斯密码 再给你一个字典(下面单词本)
用下面的单词组合成给你的摩尔斯密码, 问最多有多少种不同的组合方式。
题解分析:
1.设字符串的长度为len , 判断dp[i]处是否可达, 若可达则遍历整个单词表。
2.要先把dp[0]设为1,遍历单词表,若此单词可以在 i 处匹配则 dp[i+L] += dp[i], L(这个单词转成摩尔斯密码后的字符长度);
3.最后输出dp[len];
下面是代码:
1 #include<stdio.h> 2 #include<string.h> 3 4 char Morse[26][5]={{".-"},{"-..."},{"-.-."},{"-.."}, 5 {"."},{"..-."},{"--."},{"...."},{".."},{".---"},{"-.-"},{".-.."}, 6 {"--"},{"-."},{"---"},{".--."},{"--.-"},{".-."},{"..."},{"-"}, 7 {"..-"},{"...-"},{".--"},{"-..-"},{"-.--"},{"--.."}}; 8 9 char Dict[10005][205];//字典保存每个单词10 int dp[40005];11 int main()12 {13 int T, i, n, len, j, a;14 char str[10270], str2[270];15 scanf("%d",&T);16 while(T--)17 {18 scanf("%s",str);19 len = strlen(str);20 scanf("%d",&n);21 memset(dp,0,sizeof(dp));22 for(i=0; i<n; i++)//转化词典23 {24 Dict[i][0]=NULL;//每次到要初始化25 26 scanf("%s",str2);27 for(j=0; str2[j]; j++)28 strcat(Dict[i],Morse[str2[j]-‘A‘]);29 }30 dp[0] = 1;31 for(i=0; i<len; i++)32 {33 if(dp[i])34 {35 for(j=0; j<n; j++)36 {37 a = strlen(Dict[j]);38 39 if(strncmp(str+i,Dict[j],a) == 0)//若此处可以匹配40 dp[i+a] += dp[i];41 }42 }43 }44 printf("%d\n",dp[len]);45 }46 return 0;47 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。