Information
- ID
- 1200
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 10
- Tags
- # Submissions
- 5
- Accepted
- 4
- Uploaded By
首先明确用dfs去拼接,接下来要确定两个单词之间最小的相同前缀和后缀的长度
#include <bits/stdc++.h>
using namespace std;
string s[30];
int n,yc[30][30],vis[30],ans=0,maxx;
int mt(int x,int y){
int len2=s[x].size();
for(int i=len2-1;i>=0;i--){
int kk=i,len1=0;
while(s[x][kk]==s[y][len1]&&i<len2&&len1<s[y].size()){
len1++;
kk++;
}
if(kk==len2){
return len2-i;
}
}
return 0;
}
void dfs(int x){
bool pp=false;
for(int i=1;i<=n;i++){
if(vis[i]==2) continue;
if(yc[x][i]==0) continue;
if(yc[x][i]==s[i].size()||yc[x][i]==s[x].size()) continue;
ans+=s[i].size()-yc[x][i];
pp=true;
vis[i]++;
dfs(i);
ans-=s[i].size()-yc[x][i];
vis[i]--;
}
if(!pp){
maxx=max(maxx,ans);
}
return;
}
int main(){
char ch;
cin>>n;
for(int i=1;i<=n;i++){
cin>>s[i];
}
cin>>ch;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
yc[i][j]=mt(i,j);
}
}
for(int i=1;i<=n;i++){
if(s[i][0]==ch){
vis[i]++;
ans=s[i].size();
dfs(i);
}
}
cout<<maxx;
return 0;
}
By signing up a 追梦算法网 universal account, you can submit code and join discussions in all online judging services provided by us.