P1019 单词接龙【洛谷算法习题】

P1019 单词接龙网页链接P1019 单词接龙题目背景注意本题为上古 NOIP 原题不保证存在靠谱的做法能通过该数据范围下的所有数据。本题的难度仅代表设计算法可以通过本题原始数据的难度。本题为搜索题本题不接受 hack 数据。关于此类题目的详细内容NOIP2000 提高组 T3题目描述单词接龙是一个与我们经常玩的成语接龙相类似的游戏现在我们已知一组单词且给定一个开头的字母要求出以这个字母开头的最长的“龙”每个单词都最多在“龙”中出现两次在两个单词相连时其重合部分合为一部分例如beast和astonish如果接成一条龙则变为beastonish另外相邻的两部分不能存在包含关系例如at和atide间不能相连。输入格式输入的第一行为一个单独的整数n nn表示单词数以下n nn行每行有一个单词输入的最后一行为一个单个字符表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在。输出格式只需输出以此字母开头的最长的“龙”的长度。输入输出样例 #1输入 #15 at touch cheat choose tact a输出 #123说明/提示样例解释连成的“龙”为atoucheatactactouchoose。n ≤ 20 n \le 20n≤20。解题思路本题核心是通过深度优先搜索DFS 回溯求解最长单词接龙长度首先读取单词列表和开头字母初始化单词使用次数数组每个单词最多用2 22次从所有以指定字母开头的单词开始D F S DFSDFS每次遍历未超使用次数的单词尝试拼接寻找两单词的重合子串且重合长度小于两单词长度避免包含关系拼接后更新单词使用次数递归搜索更长的“龙”回溯时恢复使用次数全程维护并更新最长“龙”的长度。因n ≤ 20 n≤20n≤20且每个单词最多用2 22次D F S DFSDFS的枚举规模可控通过回溯枚举所有合法拼接可能精准找到符合要求的最长接龙长度。总结核心逻辑D F S DFSDFS遍历所有合法拼接路径回溯维护单词使用次数最多2 22次寻找最长接龙长度。关键操作计算单词间的重合子串长度避免包含关系拼接后递归搜索并回溯恢复状态。效率保障n ≤ 20 n≤20n≤20且单词使用次数有限D F S DFSDFS的枚举规模在可接受范围内适配题目数据范围。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvt;typedefpairll,llpll;constll N1e610;constll mod1e97;constll INF1e18;ll n,v[30],ans;string s[30];charc;voiddfs(string t){ansmax(ans,ll(t.size()));for(ll i1;in;i){if(v[i]2)continue;for(ll j1;jmin(t.size(),s[i].size());j){if(t.substr(t.size()-j)s[i].substr(0,j)){v[i];dfs(ts[i].substr(j));v[i]--;}}}}intmain(){cinn;for(ll i1;in;i)cins[i];cinc;for(ll i1;in;i){if(s[i][0]c){v[i];dfs(s[i]);v[i]--;}}coutansendl;return0;}