题解 P1019 【单词接龙】

· · 题解

单词接龙

题目描述

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

这道题需要注意三点：

1.每个单词最多在龙里出现两次

2.不能在龙里出现包含关系

3.可以有重合部分

重点来了（敲黑板）

求重合部分可以从已经在龙里的最后一个单词的最后面开始枚举（从后向前枚举）直到找到最后一个单词的一个字母和想要接龙的单词的第一个字母相等，把那个单词的字母的位置记录为k，然后从已经在龙里的那个单词从k到尾进行循环枚举，同时想要接龙的单词从头到k进行枚举，如果有不相等的一个字母就返回0，否则返回那个单词的长度 -（k + 1）

code~：

#include <bits/stdc++.h>
using namespace std;
int n, vis[100001], ans, maxn, l[100001], p;
string s[10001];
char ch;
int find(int x, int y)//是否能合并 
{
    int lx = l[x];
    int ly = l[y];
    for(int i = lx - 1; i >= 1; i--)
    {
        if(s[x][i] == s[y][0])//发现字母相等！ 
        {
            int k = 0;
            for(int j = i + 1; j <= lx - 1; j++)
            {
                k++;//同时枚举 
                if(s[x][j] != s[y][k])//有一个字母不相等就返回0 
                {
                    return 0;
                }
            }
            return ly - (k + 1);//全相等返回长度 
        }
    }
    return 0;
}
void dfs(int x)//搜索单词 
{
    for(int i = 1; i <= n; i++)
    {
        if(vis[i] < 2 && find(x, i))//不能用两次且可以接龙 
        {
            vis[i]++;//用的次数++ 
            ans += find(x, i);//加上新单词的长度 
            dfs(i);//接着这个单词继续搜 
            vis[i]--;//回溯 
            ans -= find(x, i);//回溯 
        }
    }
    if(ans > p)//求最大 
    {
        p = ans;
    }
}
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        cin>>s[i];
        l[i] = s[i].length();//存下所有单词的长度 
    }
    cin>>ch;
    for(int i = 1; i <= n; i++)
    {
        if(s[i][0] == ch)//得等于首字母才能接 
        {
            ans = l[i];//先加上首单词的长度 
            vis[i]++;//首单词用过了 
            dfs(i);
            vis[i]--;//回溯 
            if(p > maxn)//求最大 
            {
                maxn = p;
            }
        }
    }
    printf("%d", maxn);
    return 0;
}

已AC