[NOIP2000 提高组] 单词接龙题解

本文主要是介绍[NOIP2000 提高组] 单词接龙题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

[NOIP2000 提高组] 单词接龙题解

[NOIP2000 提高组] 单词接龙
这题不难，简单的dfs但需要极好的题目理解能力 ~~本蒟蒻wa哭~~
需要注意的一个普通的点：每个单词都最多在“龙”中出现两次，相信大家都不会wa在这上面吧。
最重要的也是最坑的两个点来了：
一、在两个单词相连时，其重合部分合为一部分，例如 beast 和 astonish,接成一条龙则变为 beastonish。
如果你认为只要重合就会连接起来那么就错了。实际上两个单词合并时，合并部分取的是最小重叠部分。
二、另外相邻的两部分不能存在包含关系，例如 at 和 atide 间不能相连。
最开始我以为相同的单词也不能相连，但实际上的意思是当需要连起来时两个单词完全重叠才是不合法的。
比如envelope和envelope接龙，结果是：envelopenvelope，只取最小的重叠部分‘e’。

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int vis[30],ans,n;//vis标记第i串字符使用次数 
char a[30][100];//存字符串 
int str[30];//记录第i串字符的长度 
int g[30][30];//第j个字符串接在第i个字符串后面增加的字符个数 ，当值为0时代表j不能接龙在i后 //坑点1：两个单词合并时，合并部分取的是最小重叠部分atat与tath接龙是atatath而不是atath 
void link()//g数组初始化 
{int i,j,k,F,t1,t2,t3,sum;memset(g,0,sizeof(g));for(i=0;i<n;i++){t1=str[i];for(j=0;j<n;j++){//if(i==j)continue;坑点2：自己可以接自己，但不能是完全重合的接，//比如envelope可以自己接自己，接起来为envelopenvelope//at就不合法，接起来为at自己没有变化，没有意义，还浪费一次接龙次数 t2=str[j];for(F=0;F<t2;F++){t3=t1-1, sum=0;if(a[j][F]==a[i][t3])for(k=F;k>=0;k--)//记录j字符与i字符重叠部分长度 {if(a[j][k]==a[i][t3--])	 sum++;else {sum=0;break;}}if(sum)break;}if(sum==t1||sum==t2||sum==0)g[i][j]=0;//当完全不重合以及完全重合时标记为0 else g[i][j]=str[j]-sum;}}
}void dfs(int sum,int now)//sum:字符长度 now上一个接龙单词的序号 
{for(int i=0;i<n;i++){if(vis[i]==2||!g[now][i])continue;//当单词使用不超过2次，且可以接龙时进行搜索 vis[i]++;dfs(sum+g[now][i],i);vis[i]--;}ans=max(ans,sum);//递归终止条件即找不到字符串接龙时 return ;
}int main()
{char c[10];scanf("%d",&n);for(int i=0;i<n;i++){scanf("%s",a[i]);str[i]=strlen(a[i]);}scanf("%s",c);link();ans=0;for(int i=0;i<n;i++)//寻找第一个接龙单词 {memset(vis,0,sizeof(vis));if(a[i][0]==c[0]){vis[i]++;dfs(str[i],i);}}printf("%d",ans);return 0;
}