深搜
题目特别注意的地方：每个单词最多出现两次（恶心之处，题目没有说明）
本题要点：
1、建图：
以每个单词为图的点，能接龙的两个单词，这两点就连上边。 n <= 20, 用邻接矩阵 a[i][j] 来存两个单词
重叠部分的长度， -1 表示 两个单词不能接龙。 用 链式向前星 方式存图。
2、然后就是深搜，用数组 d[i] 表示 点 i 的出现次数，来控制 dfs, 同时， 每次深搜，更新答案 ans.
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MaxN = 22, MaxM = 410;
int a[MaxN][MaxN]; // 数组 a[i][j] 表示第i个和第j个字符串的相等前后缀长度
int head[MaxN], ver[MaxM], Next[MaxM];
int d[MaxN]; // 表示某点的出现次数
int n, tot, ans;
char str[MaxN][110];
char st[2];void add(int x, int y)
{
ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
}int match(int x, int y) // 第x 个字符串 和 第y个字符串
{
int len1 = strlen(str[x]), len2 = strlen(str[y]);for(int len = 1; len < len1 && len < len2; ++len){
bool flag = true;for(int i = 0; i < len; ++i){
if(str[y][i] != str[x][len1 - (len - i)]){
flag = false;break;}}if(flag)return len;}return -1;
}void init()
{
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
a[i][j] = match(i, j);if(a[i][j] != -1){
add(i, j); }}}
}// x 表示当前要处理的第个节点, pre 表示前一个节点
void dfs(int x, int sum, int pre)
{
// printf("dfs x = %d, sum = %d, pre = %d\n", x, sum, pre);int add_len = strlen(str[x]); if(pre != -1){
add_len -= a[pre][x];// 需要减去重叠部分的长度 }ans = max(ans, sum + add_len);d[x]++;for(int i = head[x]; i; i = Next[i]){
int y = ver[i];if(d[y] > 1) continue;dfs(y, sum + add_len, x);}d[x]--;
}void solve()
{
init();for(int i = 0; i < n; ++i){
if(str[i][0] == st[0]){
memset(d, 0, sizeof d);dfs(i, 0, -1);}}printf("%d\n", ans);
}int main()
{
scanf("%d", &n);for(int i = 0; i < n; ++i){
scanf("%s", str[i]);}scanf("%s", st);solve();return 0;
}/* 5 at touch cheat choose tact a *//* 23 */