首页 > ACM题库 > HDU-杭电 > HDU 1523 Decoding Morse Sequences-动态规划-[解题报告] C++
2013
12-12

HDU 1523 Decoding Morse Sequences-动态规划-[解题报告] C++

Decoding Morse Sequences

问题描述 :

Before the digital age, the most common "binary" code for radio communication was the Morse code. In Morse code, symbols are encoded as sequences of short and long pulses (called dots and dashes respectively). The following table reproduces the Morse code for the alphabet, where dots and dashes are represented as ASCII characters "." and "-":


Notice that in the absence of pauses between letters there might be multiple interpretations of a Morse sequence. For example, the sequence -.-..– could be decoded both as CAT or NXT (among others). A human Morse operator would use other context information (such as a language dictionary) to decide the appropriate decoding. But even provided with such dictionary one can obtain multiple phrases from a single Morse sequence.

Write a program which for each data set:

reads a Morse sequence and a list of words (a dictionary),

computes the number of distinct phrases that can be obtained from the given Morse sequence using words from the dictionary,

writes the result.

Notice that we are interested in full matches, i.e. the complete Morse sequence must be matched to words in the dictionary.

输入:

The rst line of the input contains exactly one positive integer d equal to the number of data sets, 1 <= d <= 20. The data sets follow.

The first line of each data set contains a Morse sequence – a nonempty sequence of at most 10 000 characters "." and "-" with no spaces in between.

The second line contains exactly one integer n, 1 <= n <= 10 000, equal to the number of words in a dictionary. Each of the following n lines contains one dictionary word – a nonempty sequence of at most 20 capital letters from "A" to "Z". No word occurs in the dictionary more than once.

输出:

The output should consist of exactly d lines, one line for each data set. Line i should contain one integer equal to the number of distinct phrases into which the Morse sequence from the i-th data set can be parsed. You may assume that this number is at most 2 * 10^9 for every single data set.

样例输入:

1
.---.--.-.-.-.---...-.---.
6
AT
TACK
TICK
ATTACK
DAWN
DUSK

样例输出:

2

题目链接:http://poj.org/problem?id=1432

题目大意及思路:计算一段文摩斯码可能的译文种数,定义dp[i]为前i个摩斯码的种数,然后枚举最后一个单词的摩斯码长度,将所有可能加起来;要注意的是有些单词的摩斯码相同。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<queue>
#include<algorithm>
#include<vector>
#include<stack>
#include<list>
#include<iostream>
#include<map>
using namespace std;
#define inf 0x3f3f3f3f
#define Max 110
int max(int a,int b)
{
	return a>b?a:b;
}
int min(int a,int b)
{
	return a<b?a:b;
}
string rec;
char s[10100],str[10100];
int dp[10100];
int len;
char cod[26][5]={
            ".-","-...","-.-.","-..",
            ".","..-.","--.","....",
            "..",".---","-.-",".-..",
            "--","-.","---",".--.",
            "--.-",".-.","...","-",
            "..-","...-",".--","-..-",
            "-.--","--.."
            };
map<string ,int>mp;
int main()
{
    int t,n,i,j,k;
    scanf("%d",&t);
   // getchar();
 //   cout<<cod[0];
    while(t--)
    {
        mp.clear();
        memset(dp,0,sizeof(dp));
       scanf("%s",s+1);
       len=strlen(s+1);
   //    printf("len %d\n",len);
       scanf("%d",&n);
       for(i=0;i<n;i++)
       {
            scanf("%s",str);
          //  int len=strlen(str);
            string tmp;
            for(j=0;str[j];j++)
                tmp+=cod[str[j]-'A'];
           // cout<<tmp<<endl;
            mp[tmp]++;
       }
       dp[0]=1;
       for(i=1;i<=len;i++)
            for(j=i-1;j>=i-81&&j>=0;j--)
            {
                if(dp[j]==0)
                    continue;
                char a[100];
                for(k=j+1;k<=i;k++)
                {
                    a[k-j-1]=s[k];
                }
                a[k-j-1]=0;

                  //  cout<<a<<endl;
                    dp[i]+=dp[j]*mp[a];
              //  printf("i %d dp %d\n",i,dp[i]);
            }
        printf("%d\n",dp[len]);
    }
}

 

解题报告转自:http://blog.csdn.net/wings_of_liberty/article/details/7403288


  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。