原题链接如下:https://www.luogu.com.cn/problem/P1019
曾经写过这道题,那时自己是纯纯纯…纯蒟蒻,思考半天连个样例也没有过,所以就看了题解区,大片大片的都是60行+,70行+的,而自己再次思考写出的dfs只有40多行,也算是小进步!
不过说真的家人们,这道远古的NOIP提高题,有些佬说这个题目的数据有点问题,页面的超链接那里洛谷粘贴板上有专门的说明,简而言之就是ac掉全部数据的代码并不是完全正确的.
我来计算我的时间复杂度,当不考虑dfs的深度,那么最坏情况就是O(n * n * m),其中m是单词总的平均长度.如果考虑dfs的深度,假设深度为3,那么时间复杂度就是O(n * (n * m)^(3) );如果再深点,那么就会超时了.所以能过,不代表代码正确,而代表数据太弱!

代码如下:

#include <bits/stdc++.h>
using namespace std;
int n,ans = 0;
char es;
vector<string> h;
string s[23];
void dfs(string ss,map<string,int>& mp,int cnt)
{// ss : touch . 
    int ok = 1;
    for(int i = 1 ; i <= n ; i++){
        if(mp[s[i]]>=2) continue;
        string p1,p2;
        string sr = s[i];//choose
        for(int j = 1 ; j < min(sr.size(),ss.size()) ; j++){
            p2 = sr.substr(0,j);
            p1 = ss.substr(ss.size()-j,j);
            if(p2==p1) {
                mp[sr]++;
                dfs(sr,mp,cnt+sr.size()-j);
                mp[sr]--;
            }
        }
    }
    ans = max(ans,cnt);
}
int main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i++) cin >> s[i];
    cin >> es;
    for(int i = 1 ; i <= n ; i++)
        if(s[i][0] == es) h.push_back(s[i]); 
    for(string s : h) {
        map<string,int> mp;
        mp[s]++;int cnt = s.size();
        dfs(s,mp,cnt);//当前后面的字符 
    }
    cout << ans << endl;
    return 0;
}