本文主要是介绍洛谷 P1019 单词接龙，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目背景
注意：本题为上古 NOIP 原题，不保证存在靠谱的做法能通过该数据范围下的所有数据。
NOIP2000 提高组 T3
题目描述
单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast 和 astonish，如果接成一条龙则变为 beastonish，另外相邻的两部分不能存在包含关系，例如 at 和 atide 间不能相连。
输入格式
输入的第一行为一个单独的整数 n 表示单词数，以下 n 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在。
输出格式
只需输出以此字母开头的最长的“龙”的长度。
输入输出样例
输入 #1
5 at touch cheat choose tact a
输出 #1
23
说明/提示
样例解释：连成的“龙”为 atoucheatactactouchoose。
n≤20。
本题调了3个多小时才写出来，
有以下几个容易出错的地方
1，每个单词可以使用两次，
2，如果前面的龙包含后面要接的单词，这个单词不用接（接了也不增加总长度如qcr和cr）
3，单词可以不用全部用完
4，洛谷不知道什么机制不能使用 getchar();(输入开始的字符时用%s)
解题思路
本题方法深搜，搜索每一个单词，把搜索出来单词组合起来放到一个字符串数组s里面，用一个book数组标记每个单词使用的次数，按照贪心的思想，每次从s的末尾开始找是否有匹配的重合部分（保证接龙后的单词最长），dfs结束的条件是没有单词能够继续接龙下去了
代码如下
#include<stdio.h>
#include<string.h>
//top指向s的顶部，f指向v的顶部，v用来记录每次接龙除去重合部分单词的长度
int n, book[25], top = 0, v[10000], f = 0, sum = -1e9;
//a储存所有单词，b
char a[25][50], b[2], s[10000];//s为单词接龙后的组合
void dfs(int y)//直接开搜y没有特殊含义
{int i;for (i = 1; i <= n; i++)//遍历每个单词{if (book[i] < 2)//每个单词可以使用两次{int flag = 0, j;//flag标记单词是否可以接龙int k = strlen(a[i]);for (j = 0; j < k - 1; j++)//j<k-1直接排除包含情况，贪心{int h = top - 1 - j, q;if (h < 0)//s不能为空break;for (q = 0; q <= j; q++){if (a[i][q] != s[h])//如果没有重合j个字符，不能接龙break;h++;}if (h == top)//如果能够接龙{flag = 1;//标记v[f++] = k - j - 1;//求出没有重合的部分并储存break;}}if (flag == 1)//能够接龙{book[i]++;for (int u = j + 1; u < k; u++)s[top++] = a[i][u];dfs(y);//回溯一波book[i]--;top -= v[--f];}}}if (i == n + 1)//如果没有单词能够接龙，直接返回{if (top > sum){sum = top;//更新最大长度}return;}return;
}
int main()
{scanf("%d", &n);for (int i = 1; i <= n; i++)scanf("%s", a[i]);scanf("%s", &b);s[top++] = b[0];dfs(1);//dfs搜索printf("%d", sum);return 0;
}
这篇关于洛谷 P1019 单词接龙的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
