POJ 2.5 8783 && luogu p1019 单词接龙

xiaoxiao2021-02-28  5

题目描述

单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”(每个单词都最多在“龙”中出现两次),在两个单词相连时,其重合部分合为一部分,例如 beast和astonish,如果接成一条龙则变为beastonish,另外相邻的两部分不能存在包含关系,例如at 和 atide 间不能相连。

输入输出格式

输入格式:

输入的第一行为一个单独的整数n (n<=20)表示单词数,以下n 行每行有一个单词,输入的最后一行为一个单个字符,表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.

输出格式:

只需输出以此字母开头的最长的“龙”的长度

输入输出样例

输入样例#1: 5 at touch cheat choose tact a 输出样例#1: 23 (连成的“龙”为atoucheatactactouchoose)

说明

NOIp2000提高组第三题

#include<cstdio> #include<cstring> struct doo { char s[21]; int l; int v;//单词出现的次数 }c[21]; int maxn,n; void jl(int x,int l)//待连接单词的序号 l为目前单词接龙的长度 { for(int i=1;i<=n;i++)//寻找可连接单词(待连接单词后连接可连接单词) if(c[i].v<2)//每个单词最多出现两次 for(int j=0;j<c[x].l;j++)//查找待连接单词的每一位 if(c[x].s[j]==c[i].s[0])//找到可衔接的位置 { int k=1; bool t=1; for(int d=j+1;d<c[x].l&&k<c[i].l;k++,d++)//d表示待连接单词下标 k是可连接单词下标 所以在循环条件中需满足它们小于(因为不能包含,所以不能等于)单词长度 if(c[x].s[d]!=c[i].s[k])//从可衔接位置开始判断 若后面的字符并不完全匹配则无法衔接 { t=0; break; } if(t) { c[i].v++; jl(i,l+c[i].l-k);//若可以衔接 找下一个可衔接单词 接龙长度更新 加上当前连接单词的长度 减去重叠部分的长度 c[i].v--; } } if(l>maxn) maxn=l; } int main() { freopen("jl.in","r",stdin); freopen("jl.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%s",c[i].s); c[i].l=strlen(c[i].s); } scanf("%s",c[0].s); c[0].l=strlen(c[0].s);//直接将开头字母存在0下标 当作第一个单词处理 jl(0,c[0].l); printf("%d",maxn); fclose(stdin); fclose(stdout); return 0; }

转载请注明原文地址: https://www.6miu.com/read-200293.html

最新回复(0)