首页 > 代码库 > HDU 1523 Decoding Morse Sequences

HDU 1523 Decoding Morse Sequences

2024-07-15 08:01:07   221人阅读

题目链接：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 }

 


联系
我们