codevs1018 单词接龙

题目描述 Description

单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at和atide间不能相连。

输入描述 Input Description

输入的第一行为一个单独的整数n(n<=20)表示单词数，以下n行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.

输出描述 Output Description

只需输出以此字母开头的最长的“龙”的长度

样例输入 Sample Input

touch

cheat

choose

tact

样例输出 Sample Output

数据范围及提示 Data Size & Hint

（连成的“龙”为atoucheatactactouchoose）

思路：

1.考虑到问题的性质，给一堆字符串，然后让你输出拼接后的最大长度，拼接字符串其实就是字符长度在拼接，所以可以考虑预处理，把所有两个字符拼接以后隐藏掉的字符数求出来，这样再dfs就可以绕过字符处理了

2.按照题目的提法，从一个字母开始拼接，考虑头字符只能出现一次，将其剩余次数设为零，考虑到不能将某一个字串吞掉，可以在预处理的时候，将不是首字母的拼接上限设到最小的字串长度-1

代码：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<string>

using namespace std;

const int maxn = ;

int n = ,total = ,use[maxn],sub[maxn][maxn];

string words[maxn],begin;

void judgement(){

    int r1 = ,r2 = ,r3 = ;

    for(r1 = ;r1 < n;r1++){

        for(r2 = ;r2 < n;r2++){

            sub[r1][r2] = ;

            int temp = words[r1].size() < words[r2].size() ? words[r1].size(): words[r2].size();

            for(r3 = temp;r3 > ;r3--)

               if(words[r1].substr(words[r1].size() - r3,r3) == words[r2].substr(,r3)) sub[r1][r2] = r3;

        }

        cout<<endl;

    }

}

void dfs(int voc,int big){

    if(big > total) total = big;

    int r1 = ;

    for(r1 = ;r1 < n;r1++){

        if(use[r1] >  && sub[voc][r1] > ){

            use[r1]--;

            dfs(r1,big + words[r1].size() - sub[voc][r1]);

            use[r1]++;

        }

    }

}

int main(){

    cin>>n;

    int r1 = ;

    n += ;

    for(r1 = ;r1 < n;r1++){

        cin>>words[r1];

        use[r1] = ;

    }

    use[n - ] = ;

    judgement();

    dfs(n-,);

    cout<<total + ;

    return ;

}

巴特西

codevs1018 单词接龙

题目描述 Description

最新文章

热门文章