本文主要是介绍NOIp2000提高组-单词接龙（dfs），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：https://www.luogu.org/problemnew/show/P1019
思路：首先要知道两个单词合并时，合并部分取的是最小重叠部分，相邻的两部分不能存在包含关系就是说如果存在包含关系，就不能标记为使用过，每个单词最多出现两次。搜索的时候开个vis标记数组，用来标记每个单词使用的次数，从开头字母开始搜索，两层for，第一层for搜索每一个单词，第二层for是判断我们搜索的单词的第几位和枚举的单词的首字母相同，比如搜索的单词是touch，当遍历到cheat这个单词时发现touch的第四位和枚举的单词cheat相同时，我们用while循环找出重叠部分长度，那么当前的长度就是 = 当前长度 + 枚举单词长度 - 重叠部分的长度。回溯的时候vis标记减一，恢复长度就好了。注意初始化now为1，因为开头是单个字母。
AC代码：
#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;
}
这篇关于NOIp2000提高组-单词接龙（dfs）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
