传送至原题>>
这是NOIP2000提高组的原题
首先说说题面：
现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的字符串（“龙”）（每个单词都最多在字符串中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast和astonish，如果接成一条龙则变为beastonish。
输入
输入的第一行为一个单独的整数n (n<=20)表示单词数，以下n 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。保证龙一定存在。
输出
只需输出以此字母开头的最长的“龙”的长度
样例输入
5
at
touch
cheat
choose
tact
a
样例输出
23
样例解释
依次把at,touch,cheat,tact,tact,touch,choose连成“龙”为atoucheatactactouchoose
好了，现在说说思路——
我相信很多人都会认为这道题要用枚举，但这道题确实就是枚（深）举（搜）。
//关于深搜的过程和框架我会在后面的文章里说
每次从1到n枚举每个单词，如果这个单词在当前“龙”中最多出现了一次（不是两次，而是一次！因为你需要保证在接上这个单词后“龙”里这个单词最多出现了两次），那就在当前“龙”中接上，再不断往下搜索，直到无法再往龙上接单词，就把当前“龙”的长度与最大长度比较，让后往回走，枚举出所有的情况。
具体的解释会在程序里说明。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
char a[20][20],s[400];
int n,f[20],maxx;
void dfs(int la)//la是上一次接的单词的长度，因为没有接所以初始是0
{
int ls=strlen(s);//s当前的“龙”
maxx=max(ls,maxx);//选最大
for (int i=ls-1;i>=ls-la-1;i--)//看从“龙”的第i位开始可不可以接。但是我也不知道为什么要写到最外层
for (int j=1;j<=n;j++)//j枚举单词
if (f[j]<2)
{
int ff=0;//判断可不可以接
for (int k=0;k<ls-i;k++)
if (a[j][k]!=s[i+k])
{
ff=1; break;
}
if (!ff)//如果可以接，就往下继续搜索
{
s[i]='\0';因为是从i位接的，所以第i位就要结束，并把单词接在后面
strcat(s,a[j]);
f[j]++;//当前单词出现次数+1
dfs(strlen(a[j]));//继续搜索
s[ls]='\0';//这就是回溯：因为往下枚举的时候又要重新开始，要把s还原，所以这个单词的出现次数也要-1
f[j]--;
}
}
}
int main()
{
scanf("%d\n",&n);
for (int i=1;i<=n;i++)
scanf("%s",&a[i]);
scanf("\n%c",&s[0]);
dfs(0);
printf("%d",maxx);
return 0;
}