AcWing 1117. 单词接龙(记忆化搜索)
原题链接
简单
作者:
O₂
,
2024-11-10 20:07:59
,
所有人可见
,
阅读 2
#include<bits/stdc++.h>
using namespace std;
map<string,int>f;
const int N=30;
int n,res,cnt[N];
string s[N];
char c;
int check(string s1,string s2){ //判断连接长度
string now1="",now2="";
for(int i=s1.size()-1,j=1;i>=0&&j<s2.size();i--,j++){
now1=s1[i]+now1;
now2+=s2[j-1];
if(now1==now2) return j;
}
return -1;
}
int dfs(string path){
if(f.count(path)) return f[path]; //记忆化
//cout<<path<<endl;
int res=path.size(); //初始化
for(int i=1;i<=n;i++){
if(!cnt[i]) continue;
int ans=check(path,s[i]);
if(ans!=-1){
string last=path;
path+=s[i].substr(ans);
cnt[i]--;
res=max(res,dfs(path));
cnt[i]++;
path=last;
}
}
return f[path]=res;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>s[i];
cnt[i]=2; //记录目前可用数量
}
cin>>c;
for(int i=1;i<=n;i++){
if(s[i][0]==c){
for(int j=1;j<=n;j++) cnt[j]=2;
cnt[i]=1;
res=max(res,dfs(s[i]));
}
}
cout<<res<<endl;
return 0;
}