记录编号	273402	评测结果	AAAAAAAAA
题目名称	[NOIP 2000PJ]单词接龙	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2016-06-20 20:48:15	内存使用	0.79 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
using namespace std;
char ss[22][23333];
int vis[21];
int n;
int res = -1;
char first;
int last[2333];
int fifp[21];
int mf = 0;
int len[21];

#ifdef __linux__
FILE *fin_ = fopen("dcjl.in", "r"); 
FILE *fout_ = fopen("dcjl.out", "w"); 
#define fin fin_
#define fout fout_
#else
#define fin stdin
#define fout stdout	
#endif

void pre()
{
	for(int i = 0; i < n; i++){if(ss[i][0] == first)fifp[mf++] = i;len[i] = strlen(ss[i]);}	
}

void dfs(int c, int tot)
{
	res = max(res, tot);
	{
		int ll = len[last[c]];
		for(int i = 0; i < n; i++)
		{
			if(vis[i] > 1)continue;
			int cl = len[i];
			for(int j = 1; j < ll; j++)
			{
				if(!strncmp(ss[last[c]]+j, ss[i], ll-j))
				{
					vis[i]++;
					last[c+1] = i;
					dfs(c+1, tot+cl-ll+j);
					vis[i]--;
				}
			}
		}
	}
}

void work()
{
	for(int i = 0; i < mf; i++)
	{
		vis[fifp[i]] = 1;
		last[1] = fifp[i];
		dfs(1, len[fifp[i]]);
		vis[fifp[i]] = 0;
	}
}

int main()
{	
	fscanf(fin, "%d", &n);
	for(int i = 0; i < n; i++)
		fscanf(fin, "%s", ss[i]);
	fscanf(fin, "%s", ss[21]);
	first = ss[21][0];
	pre();
	work();
	fprintf(fout, "%d\n", res);
	return 0;
}