莫欺少年穷，修魔之旅在这开始—>算法提高课题解

保姆级注释，看不懂你炸我

思路：

1. 本题核心就是处理哪些单词之间可以匹配，并把可以匹配的最小值赋给它们
2. 全局变量 ans 表示连接成的最长的字符串
3. 枚举所有单词，观察是否有符合条件的单词，然后 dfs 它们
4. 回溯的时候别忘了恢复现场，即 used[last] --;

#include<bits/stdc++.h>

using namespace std;

const int N = 25;

int n,ans;
int g[N][N],used[N];
char start;
string word[N];

void dfs(string dragon,int last)
{
    //比较新字符串的长度大小
    ans=max(ans,(int)dragon.size());

    //表示word[i]又使用一次
    used[last]++;

    //枚举所有单词，看是否有单词能与当前单词匹配
    for(int i=0;i<n;i++)
        if(g[last][i]&&used[i]<2)
            dfs(dragon+word[i].substr(g[last][i]),i);

    //恢复现场       
    used[last]--;
}

int main()
{
    cin>>n;

    for(int i=0;i<n;i++) cin>>word[i];

    cin>>start;

    //预处理哪些单词之间可以匹配，且把可以匹配的最小值赋给它们
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            for(int k=1;k<min(word[i].size(),word[j].size());k++)
                if(word[i].substr((int)word[i].size()-k,(int)word[i].size())==word[j].substr(0,k))
                    {
                        g[i][j]=k;
                        break;
                    }

    //枚举所有单词，观察哪个单词可以与初始字母匹配
    for(int i=0;i<n;i++)
        if(word[i][0]==start)
            dfs(word[i],i);

    cout<<ans<<endl;

    return 0;
}