3 solutions
-
1
#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