本文主要是介绍洛谷 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 单词接龙的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!