首页 > > 程序设计 > C/C++ >

NOIP2000 提高组 T3 单词接龙

2018-09-10 00:58:15来源：博客园阅读 ()

题面

单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如

输入输出格式

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

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

样例：

5
at
touch
cheat
choose
tact
a

输入

输出

思路

首先用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;
}