4 solutions

  • -1
    @ 2025-5-10 10:27:05
    #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
44
Accepted
8
Uploaded By