本文主要是介绍洛谷 P1019 [NOIP2000 提高组] 单词接龙，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
参考代码
#include <bits/stdc++.h>
using namespace std;
string s[25];
int vis[25], ans, now = 1, n;
void dfs(int k)
{
ans = max(ans, now);
for(int i = 1; i <= n; i++)
if(vis[i] < 2)
{
for(int j = 0; j < s[k].length(); j++)
if(s[i][0] == s[k][j])
{
int cnt1 = j, cnt2 = 0;
while(s[i][cnt2]==s[k][cnt1]&&cnt1<s[k].length())cnt1++,cnt2++;
if(cnt1 >= s[k].length())
{
vis[i]++;
now += s[i].length() - cnt2;
dfs(i); vis[i]--;
now -= s[i].length() - cnt2;
}
}
}
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i++)
cin >> s[i]; cin >> s[0];
dfs(0); cout << ans << endl;
}
思路：首先要知道两个单词合并时，合并部分取的是最小重叠部分
相邻的两部分不能存在包含关系就是说如果存在包含关系，就不能标记为使用过，每个单词最多出现两次
搜索的时候开个vis标记数组，用来标记每个单词使用的次数，从开头字母开始搜索，两层for，第一层for搜索每一个单词
第二层for是判断我们搜索的单词的第几位和枚举的单词的首字母相同
比如搜索的单词是touch，当遍历到cheat这个单词时发现touch的第四位和枚举的单词cheat相同时
我们用while循环找出重叠部分长度
那么当前的长度就是 = 当前长度 + 枚举单词长度 - 重叠部分的长度
回溯的时候vis标记减一，恢复长度就好了。注意初始化now为1，因为开头是单个字母。
这篇关于洛谷 P1019 [NOIP2000 提高组] 单词接龙的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
