原題傳送門

思路

這道題主要考察搜索與字符串處理的能力，但也能在答案中看到圖論思想的影子，所以這是一道比較考察范圍比較廣的題目。
這道題的重點其實在于字符串處理，即用盡可能少的時間復雜度分辨兩個單詞是否可以接龍，搜索方面無需優化，只要字符串處理函數比較快，大爆搜也可以輕松AC，因此，這道搜索題其實實在考察字符串。

Code

#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<stack>
#include<map>
using namespace std;

int e[41][41],b[41]; 
int i,j,n,maxl;
string w[41];

int l(string a,string b)
{
	for(int i=1;i<=a.length();i++)
	{
		string t=a.substr(a.length()-i,i);
    	if(t.length()<=b.length()&&t==b.substr(0,t.length()))
				return b.length()-t.length();
	}
	return 0;
}

void dfs(int no,int l)
{
	if(l>maxl)
		maxl=l;
	int i;
	b[no]=1;
	for(i=0;i<=2*n;i++)
	{
		if(b[i]==0&&e[no][i]>0)
		{
			dfs(i,l+e[no][i]);
		}		
	}
	b[no]=0;
}

int main()
{
    cin>>n;
    for(i=1;i<=n;i++)
    {
		cin>>w[i]; 
		w[i+n]=w[i];
	}
    cin>>w[0];
    for(i=0;i<=2*n;i++)
    	for(j=0;j<=2*n;j++)
    		e[i][j]=l(w[i],w[j]);
    dfs(0,1);
    cout<<maxl;
    return 0;
}