2011-06-14 22:27:19Morris
d871. NOIP2000 4.单词接龙
http://zerojudge.tw/ShowProblem?problemid=d871
单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at和atide间不能相连。
輸入說明
：
输入的第一行为一个单独的整数n(n<=20)表示单词数，以下n行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.
輸出說明
：
只需输出以此字母开头的最长的“龙”的长度
範例輸入 ：
5 at touch cheat choose tact a
範例輸出 ：
23
提示
：
连成的“龙”为 atoucheatactactouchoose
出處
：
/**********************************************************************************/
/* Problem: d871 "NOIP2000 4.单词接龙" from NOIP2000普及组第四题、提高组第三题*/
/* Language: C */
/* Result: AC (2ms, 269KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-13 18:44:10 */
/**********************************************************************************/
#include<stdio.h>
#include<string.h>
char idiom[20][300];
int Map[20][20], Used[20], l[20], Max, n;
void Build(int n) {
int a, b, c, d, k;
Max = 0;
for(a = 0; a < n; a++) {
for(b = 0; b < n; b++)
Map[a][b] = 0;
l[a] = strlen(idiom[a]);
Used[a] = 0;
}
for(a = 0; a < n; a++)
for(b = 0; b < n; b++) {
for(k = 1; k <= l[a]; k++) {
for(c = 0, d = l[a]-k; c < k; c++, d++)
if(idiom[a][d] != idiom[b][c])
break;
if(c == k) break;
}
if(k <= l[a])
Map[a][b] = l[b] - k;
}
}
void DFS(int now, int sum) {
int a;
if(sum > Max) Max = sum;
for(a = 0; a < n; a++)
if(Map[now][a] > 0 && Used[a] < 2) {
Used[a]++;
DFS(a, sum+Map[now][a]);
Used[a]--;
}
}
main() {
int a;
char st[2];
while(scanf("%d", &n) == 1) {
for(a = 0; a < n; a++)
scanf("%s", &idiom[a]);
scanf("%s", st);
Build(n);
for(a = 0; a < n; a++)
if(idiom[a][0] == st[0]) {
Used[a] = 1;
DFS(a, l[a]);
Used[a] = 0;
}
printf("%d\n", Max);
}
return 0;
}