欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

NOIP2000 提高组 T3 单词接龙

程序员文章站 2022-04-18 11:53:01
题面 单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”(每个单词都最多在“龙”中出现两次),在两个单词相连时,其重合部分合为一部分,例如 beastbeast和astonishastonish,如果接成一条龙则变为bea ......

题面

单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”(每个单词都最多在“龙”中出现两次),在两个单词相连时,其重合部分合为一部分,例如 beastbeast和astonishastonish,如果接成一条龙则变为beastonishbeastonish,另外相邻的两部分不能存在包含关系,例如atat 和 atideatide 间不能相连。

输入输出格式

输入格式:

输入的第一行为一个单独的整数nn (n \le 20n20)表示单词数,以下nn 行每行有一个单词,输入的最后一行为一个单个字符,表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.

输出格式:

只需输出以此字母开头的最长的“龙”的长度.

样例:

NOIP2000 提高组 T3 单词接龙
5
at
touch
cheat
choose
tact
a
输入
NOIP2000 提高组 T3 单词接龙
23
输出

思路

首先用calc数组记录x到y的最短重合部分。然后dfs即可,t数组先赋值,再开个flag记录还可不可以再连,若可以就连,不可以就更新max值.

代码

#include<bits/stdc++.h>
using namespace std;
string s[25];
char start;
int n,t[25],len[25],calc[25][25],maxx=-1,ans=0;
int pub(int x, int y){
    bool f=1; 
    int top=0;
    for(int i=len[x];i>=0;i--)
    {
        f=1;
        for(int j=i;j<=len[x];j++) if(s[x][j]!=s[y][top++]){f=0;break;}
        if(f==1) return len[x]-i+1;        
        top=0;
    }
    return 0;
}
void dfs(int x)
{
    bool flag=false; 
    for (int i=1;i<=n;i++)
    {
        if (t[i]==0) continue;
        if (calc[x][i]==0) continue;
        if(calc[x][i]==len[x]+1||calc[x][i]==len[i]+1) continue;
        t[i]--;
        ans+=len[i]+1-calc[x][i];
        flag=true;
        dfs(i);
        t[i]++;
        ans-=len[i]+1-calc[x][i];
    }
    if(flag==false) maxx=max(maxx,ans);
}
int main()
{
    cin>>n;    
    for (int i=1;i<=n;i++) t[i]=2;
    for (int i=1;i<=n;i++) cin>>s[i],len[i]=s[i].size()-1;
    cin>>start;
//  for (int i=1;i<=n;i++) cout<<s[i]<<" "<<len[i]<<endl;
    for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) calc[i][j]=pub(i,j);
//    for (int i=1;i<=n;i++) 
//    { 
//      for (int j=1;j<=n;j++)
//        cout<<calc[i][j]<<" ";
//      cout<<endl;
//    }
    for (int i=1;i<=n;i++) if (s[i][0]==start) t[i]--,ans=len[i]+1,dfs(i),t[i]=2;
    cout<<maxx<<endl;
}