P1019单词接龙

· · 个人记录

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

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

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

输入输出样例 输入样例#1： 5 at touch cheat choose tact a 输出样例#1： 23 说明 （连成的“龙”为atoucheatactactouchoose）

NOIp2000提高组第三题

本题思路解析：刚拿到题肯定想直接dfs咯，的确就是这样的。。。为什么会这么想呢，因为你并不知道选取哪两个先合并，也没有贪心的想法可以告诉你先合并谁，我们只有一个一个试。不过这道题的dfs是有技巧的，（其实就是让代码更自然好懂一点。。），我们设计一个canlink函数，返回值是可以拼接的最小长度。为什么要最小长度呢？这里就是一个贪心的思想了，你每次拼接后加上的长度都是新单词的长度-重合部分的长度，那么重合的越少当然越好。其实就没了，一旦贪心想到这题就直接dfs就好了。。。

上代码

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
string str[20];
int use[20],length = 0,n;
int canlink(string a,string b){
    for(int i=1;i < min(a.length(),b.length());i++){
        int flag = 1;//在外层循环设置，每次检查完一个字母位，进入第二个循环时清零
        for(int j=0;j<i;j++){//j不能等于i，因为a[a.length()]位置不存在
        if(a[a.length()-i+j]!=b[j]) flag = 0;

    }if(flag) return i;//这里用到了贪心，一旦搜索到最短的公共字符串便返回长度，这样减少的少 

} return 0;//无公共部分 
}
void dfs(string s,int lengthnow){
    length = max(lengthnow,length);
    for(int i=0;i<n;i++){
        if(use[i]>=2) continue;
        int c =canlink(s,str[i]); 
        if(c > 0){
            use[i]++;
            dfs(str[i],lengthnow+str[i].length()-c);
            use[i]--;
        }
    }
} 
int main(){
    scanf("%d",&n);
    for(int i=0;i<=n;i++){
        use[i]=0;
        cin>>str[i];//printf("%s",&str[i])是不能成功的 
    }

        dfs(' '+str[n],1);

    printf("%d",length);
}