3 solutions

  • 1
    @ 2024-8-9 15:20:24
    #include<bits/stdc++.h>
    using namespace std;
    const int N=25;
    string word[N];
    int dist[N][N]; //dist[i][j]=k 表示s[i]和s[j]的最短公共长度位k 
    int used[N]; //使用次数 
    int n;
    int maxv;
    void dfs(string dragon,int last)
    {
        maxv=max(maxv,int(dragon.size())); //更新长度  
        for(int i=0;i<n;i++) //枚举单词 
        {
            if(dist[last][i]&&used[i]<2) //如果可以拼接且使用次数少于两次
            {
                used[i]++;  //i的使用次数增加一次
                dfs(dragon+word[i].substr(dist[last][i]),i); //继续搜索
                used[i]--; //换个分支,使用次数减少
            }
        }
    }
    int main()
    {
        cin>>n;
        for(int i=0;i<n;i++)
            cin>>word[i];
        char ch;
        cin>>ch; //开始字符 
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
            {
                string a=word[i],b=word[j];
                for(int k=1;k<min(a.size(),b.size());k++)
                {
                    if(a.substr(a.size()-k,k)==b.substr(0,k)) //判断a的后缀和b的前缀是否相等 
                    {
                        dist[i][j]=k; //记录长度然后跳出 
                        break;
                    }
                }
            }
        for(int i=0;i<n;i++)
        {
            if(word[i][0]==ch) //如果是以龙开头的但是 
            {
                used[i]++;  //i使用了一次
                dfs(word[i],i); //开始搜索 
                used[i]--; //换个单词
            }
        }
        cout<<maxv;
        return 0;
    }
    
    

    Information

    ID
    1011
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    7
    Tags
    (None)
    # Submissions
    40
    Accepted
    6
    Uploaded By