Decoding Morse Sequences

题目链接：

http://acm.hust.edu.cn/vjudge/contest/129783#problem/D

Description

Input

Sample Input

Sample Output

Source

##题意：

##题解：

##代码：
``` cpp
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
#define eps 1e-8
#define maxn 10010
#define mod 100000007
#define inf 0x3f3f3f3f3f3f3f3f
#define mid(a,b) ((a+b)>>1)
#define IN freopen("in.txt","r",stdin);
using namespace std;

string Morse[26] = {{".-"},{"-..."},{"-.-."},{"-.."},{"."},{"..-."},{"--."},

{"...."},{".."},{".---"},{"-.-"},{".-.."},{"--"},{"-."},{"---"},{".--."},

{"--.-"},{".-."},{"..."},{"-"},{"..-"},{"...-"},{".--"},{"-..-"},{"-.--"},{"--.."}

};

int n;

char text[maxn];

int dp[maxn];

map<string, int> mp;

int main(int argc, char const *argv[])

{

//IN;

int t; cin >> t;

while(t--)

{

    scanf("%s", text+1);

    scanf("%d", &n);

    mp.clear();

    for(int i=1; i<=n; i++) {

        char word[25];

        scanf("%s", word);

        string cur;

        for(int i=0; word[i]; i++) {

            cur += Morse[word[i] - 'A'];

        }

        mp[cur]++;

    }

    int len = strlen(text+1);

    memset(dp, 0, sizeof(dp));

    dp[0] = 1;

    for(int i=1; i<=len; i++) {

        for(int j=max(0,i-85); j<i; j++) if(dp[j]){

            char cur[100] = {0};

            for(int k=j+1; k<=i; k++) {

                cur[k-j-1] = text[k];

            }

            dp[i] += dp[j] * mp[cur];

        }

    }

    printf("%d\n", dp[len]);;

}

return 0;

}

maxn