P1019 [NOIP2000 提高组] 单词接龙
作者:
Air1222
,
2024-04-10 11:13:05
,
所有人可见
,
阅读 7
//不认真读题的下场,debug了半天,服了
//1.不能有包含关系,2.贪心策略,每次都让重叠部分最小
//洛谷不return 0会RE;
#include <iostream>
#include <cstring>
using namespace std;
const int N = 25;
int n;
int used[N];
int ans;
string s[N];
int len(int a,int b)
{
int x=s[a].size();
int y=s[b].size();
for(int k=1;k<min(x,y);k++)
{
bool mark=true;
for(int i=x-k,j=0;i<x&&j<k;i++,j++)
if(s[a][i]!=s[b][j])
{
mark=false;
break;
}
if(mark) return k;
}
return 0;
}
void dfs(int u,int last,int sum)
{
ans=max(ans,sum);
for(int i=0;i<n;i++)
{
if(used[i]<2)
{
int x=len(last,i);
if(x)
{
used[i]++;
dfs(u+1,i,sum+s[i].size()-x);
used[i]--;
}
}
}
}
int main()
{
cin>>n;
char st;
for(int i=0;i<n;i++)
cin>>s[i];
cin>>st;
for(int i=0;i<n;i++)
{
if(s[i][0]==st)
{
used[i]++;
dfs(0,i,s[i].size());
used[i]--;
}
}
cout<<ans;
return 0;
}