https://www.luogu.org/problem/P1019

#include<cstdio> #include<cstring> #include<iostream> using namespace std; char s[50][15]; int check(int x,int y) { for(int i=strlen(s[x])-1;i>=0;i--)//从后往前比，这样能够找到最小的重合 { int j=i; int k=0;//第一个单词x从i往最后比，第二个单词从头开始比 while(s[x][j]==s[y][k]&&j<strlen(s[x])&&k<strlen(s[y]))//如果两个单词的对应位置相同并且都没有出去（过了最大的长度） { j++; k++;//那么都到下一位 } if(j==strlen(s[x]))return strlen(s[x])-i;//如果出来的时候第一个单词已经比完了，就说明可以匹配上了，返回重合的长度 } return 0; } int n; int vis[30]; int ans; int f[105][105]; void dfs(int len,int wz) { for(int i=1;i<=n;i++) { int tmp=f[wz][i];//再次把两个单词之间的连接长度取出 if(vis[i]!=2&&tmp)/如果用了没过两次还能连，就连上试试 { vis[i]++;//用了一次 dfs(len+strlen(s[i])-tmp,i);//长度变成了新连接上的单词的长度减去两个单词重合的长度，龙的最后一个单词变成了i vis[i]--;//恢复现场 } } ans=max(ans,len);//每次都要更新 } void init() { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { int tmp=check(i,j);//检查两个单词的重合程度 if(tmp&&tmp!=strlen(s[i])&&tmp!=strlen(s[j]))//如果两个单词有重合并且不是一个完全包括了另外一个 { f[i][j]=tmp;//那么就可以记录下来了 } } } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%s",s[i]); } init();//预处理，将每两个单词之间能不能接，如果能接，接了多长记录下来 char head; cin>>head;//读入龙头 for(int i=1;i<=n;i++) { if(s[i][0]==head)//如果有一个单词可以接到脖子位置 { vis[i]++;//那么这个单词首先被用了一次 dfs(strlen(s[i]),i);//从脖子长度（包含了头），脖子在零件库s中的位置开始 vis[i]--;//别忘了这里的返回现场也不能疏忽 } } printf("%d\n",ans); return 0; }