广州C++信奥老师解1913：【00NOIP普及组】单词接龙
【题目描述】
【输出】
样例连成的“龙”为atoucheatactactouchoose
#include <bits/stdc++.h>
using namespace std;
int v[21],ans=0,n;
string a[21];
int getPos(string s1,string s2) //beast和astonish 例 ast 则返回位置2,但实际把后面onish接上去
{
for(int i=0; i< min(s1.size(),s2.size()); i++)
if( s1.substr(s1.size()-i-1) ==s2.substr(0,i+1) )
return i;
return -1;
}
void dfs(string s)
{
ans=max(ans,(int)s.size()); //求取龙的最长长度
for(int i=1;i<=n;i++)
{
if(v[i]>=2) //已经使用过单词两次
continue;
int pos=getPos(s,a[i]);
if(pos!=-1) //能接上
{
v[i]++;
dfs( s+ a[i].substr(pos+1) );//beast和astonish 例 ast 则返回位置2,但实际把后面onish接上去
v[i]--; //回溯
}//if
}//for
}
int main()
{
cin>>n;
for(int i=1; i<=n; i++)
cin>>a[i];
string s;
cin>>s;
dfs(s);
cout<<ans;
return 0;
}