本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2021-07-06 06:07:00

前言

看了看其他题解，得出了一个结论：我太菜了，根本看不懂。。。

经过自己一番瞎搞，竟然做出来了？！

0.基本变量

int n,ans=0; \/\/ans是储存最终答案最大值
struct word \/\/记录一个单词的基本信息
{
	char begin,end; \/\/起止字符
	int size; \/\/长度
	bool vis; \/\/是否被搜索过
	word(){vis=0;} \/\/初始化
}a[17];

1.暴搜过样例

首先，根据题意，我们很容易想到一种暴搜方案：

int dfs(int now,int num) \/\/now:当前单词编号 num:之前的单词长度和
{
	int flag=a[now].end,len=num+a[now].size,res=len;
	\/*
	flag:储存当前单词的终止字符，用来筛选下一个单词
	len:储存包括当前单词的单词长度和
	res:储存经过当前单词的最佳答案
	*\/
	a[now].vis=1; \/\/标记
	for(int i=1;i<=n;i++)
		if(a[i].begin==flag&&!a[i].vis)
			res=max(res,dfs(i,len)); \/\/更新最佳答案
	a[now].vis=0; \/\/回溯
	return res; \/\/完结
}

这样，我们就愉快地得到了70分

2.优化出奇迹

为什么会超时呢？

当数据出现形如

ABBBBBA
ABBBBA
ABBBA
ABBBBBBA
ABBBA

的数据时，我们的暴搜会把每一个都搜一遍，直接达到了最高复杂度 $n!$ ，所以面对这种情况，我们可以用贪心的方法，对于首尾字母相同的单词，每次选最长的。

那我们肯定不能每次选单词时都算一遍最大值，于是我们进行一个sort的预处理：

bool cmp(word a,word b){return a.size>b.size;}

sort(a+1,a+n+1,cmp);

提前按照长度从大到小排序，这样就能保证拥有同样首尾字母的单词中首先被选的一定是最长的。

当我们搜索到一个单词时，面对同样尾字母的下一个单词（首字母肯定都和当前单词的尾字母一样），最长的总比短的要好，而我们通过排序已经保证了第一个选的是最长的，所以选了一个后，相同尾字母的其他单词就都不用考虑，所以我们要做一个标记，标记char done[17]，done[i]储存第$i$个被选中的单词尾字母，那么与它有同样尾字母的就不用选了。于是我们在搜索中加入判断

bool go_on=1;
\/\/count是done数组的长度
for(int j=1;j<=count;j++) \/\/遍历done数组每一个元素
	if(a[i].end==done[j]) \/\/判断此单词的尾字母在done中出现
	{
		go_on=0;
		break;
	}

和标记

if(go_on) \/\/如果done中没有出现该尾字母，就递归搜索，并把该尾字母加入done中
{
	res=max(res,dfs(i,len));
	done[++count]=a[i].end;
}

哦，别忘了初始化(这个不用解释了吧)

int count=0,done[17];
for(int i=1;i<=16;i++)
	done[i]='?';

这样，我们就得到了一份完整的AC代码

#include<bits\/stdc++.h>
using namespace std;
int n,ans=0;
struct word
{
	char begin,end;
	int size;
	bool vis;
	word(){vis=0;}
}a[17];
bool cmp(word a,word b){return a.size>b.size;}
int dfs(int now,int num)
{
	int flag=a[now].end,len=num+a[now].size,res=len;
	int count=0,done[17];
	for(int i=1;i<=16;i++)
		done[i]='?';
	a[now].vis=1;
	for(int i=1;i<=n;i++)
	{
		if(a[i].begin==flag&&!a[i].vis)
		{
			bool go_on=1;
			for(int j=1;j<=count;j++)
				if(a[i].end==done[j])
				{
					go_on=0;
					break;
				}
			if(go_on)
			{
				res=max(res,dfs(i,len));
				done[++count]=a[i].end;
			}
		}
	}
	a[now].vis=0;
	return res;
}
int main()
{
	string s;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>s;
		a[i].begin=s[0],
		a[i].end=s[s.size()-1],
		a[i].size=s.size();
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		a[i].vis=1;
		ans=max(ans,dfs(i,0));
		a[i].vis=0;
	}
	cout<<ans<<endl;
	return 0;
}

完结撒花～