结果一开O2就过了

一开始狂想dp，然而图不是DAG，结果竟是暴搜......

单词里不单只有小写字母！！单词里不单只有小写字母！！单词里不单只有小写字母！！重要的事情说三遍！！！！

回复 @Rapiz :
包含的意思是在接上后长度不增加

竟然因为没有输出文件而没能一遍过。。，我果然还是太蒟蒻了Orz...

求解第一个点
in:
1
envelope
e
ans:
15
它的意思是最长龙为envelopenvelope
但envelope显然包含它自身，所以根据题意是不能相连的。求解释？
- - -
AC辣不管怎么样，把单词错1...k位比较，如果匹配并可以让龙变长，接龙就行了。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<set>
#include<map>
#include<vector>
#include<queue>
#define maxn 45
using namespace std;
int i,j,k,m,n,ans=0,jie[maxn][maxn];
char c;
string a[maxn];
bool vis[maxn];
int lian(string a,string b){
int x=min(a.size(),b.size()),len=0;
if(a!=b&&a.substr(a.size()-x,x)==b.substr(0,x))return 0;
for(int i=1;i<x;i++){
string s1=a.substr(a.size()-i,i),s2=b.substr(0,i);
if(s1==s2){len=i;break;}
}
return len;
}
int dfs(int x){
int ans=a[x].size();
for(int i=0;i<2*n;i++){
if(!vis[i]&&jie[x][i]){
vis[i]=1;
ans=max(ans,(int)a[x].size()+dfs(i)-jie[x][i]);
vis[i]=0;
}
}
return ans;
}
int main(){
// freopen("0.txt","r",stdin);
freopen("dcjl.in","r",stdin);
freopen("dcjl.out","w",stdout);
cin>>n;
for(i=0;i<2*n;i+=2){cin>>a[i];a[i+1]=a[i];}
for(i=0;i<2*n;i++)
for(j=0;j<2*n;j++)jie[i][j]=lian(a[i],a[j]);
cin>>c;
for(i=0;i<2*n;i+=2){
if(a[i][0]==c){
vis[i]=1;
ans=max(dfs(i),ans);
vis[i]=0;
}
}
cout<<ans;
return 0;
}

Orzz一楼大神。一句话点醒梦中人

求代码

注意!!一样的前驱和后缀一定要尽量短,因为题目要求最大长度!!