记录编号	310969	评测结果	AAAAAAAAA
题目名称	[NOIP 2000PJ]单词接龙	最终得分	100
用户昵称	核糖核酸	是否通过	通过
代码语言	C++	运行时间	0.016 s
提交时间	2016-09-23 19:37:45	内存使用	0.26 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
int n, ans;
char s[25][50];
int link[25][25];
int use[25];

void Input() {
	scanf("%d", &n);
	for(int i=1; i<=n; i++) scanf("%s", s[i]);
	scanf("%s", s[0]);
}

void Build_link() {
	memset(link, -1, sizeof(link));
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++) {
			int l1=strlen(s[i]), l2=strlen(s[j]);
			for(int k=1; k<l1; k++) {
				if(k >= l2) break;
				bool flag = true;
				for(int o=0,l=l1-k; l<l1; l++,o++)
					if(s[i][l] != s[j][o]) {
						flag = false;
						break;
					}
				if(flag == true) {
					link[i][j] = l1 + l2 - k;
					break;
				}
			}
		}
}

void DFS(int p, int len) {
	ans = max(ans, len);
	for(int j=1; j<=n; j++)
		if(link[p][j]>0 && use[j]<2) {
			use[j]++;
			DFS(j, len+link[p][j]-strlen(s[p]));
			use[j]--;
		}
}

void Solve() {
	ans = 0;
	for(int i=1; i<=n; i++) use[i] = 0;
	for(int i=1; i<=n; i++)
		if(s[i][0] == s[0][0]) {
			use[i]++;
			DFS(i, strlen(s[i]));
			use[i]--;
		}
	printf("%d", ans);
}

int main () {
	freopen("dcjl.in","r",stdin);
	freopen("dcjl.out","w",stdout);
	
	Input();
	Build_link();
	Solve();
	
	fclose(stdin); fclose(stdout);
	return 0;
}