专栏首页glm的全栈学习之路洛谷 P1019 单词接龙

洛谷 P1019 单词接龙

题目链接

题目描述

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

这道题需要注意三点:

1.每个单词最多在龙里出现两次

2.不能在龙里出现包含关系

3.可以有重合部分

很明显,第一个要接的单词必须首字母是给出的字母,dfs的入口就是满足这个条件的字符串,答案就是这些字符串去dfs找出的最大值,如何dfs?接下来的单词前一部分必须是上一个已经在龙里面的单词的某个后缀,那就去遍历上一个单词从尾开始找,找到一个字符和要接的单词的开头一样,ok接着找,其中一旦发现有某个字符不一样那就不能接龙,如果都可以就返回新增的长度,不如auto,utoh,随便举个例子,找到一个字符和要接的单词一样的位置是u,新增长度是要接的字符长度减去公共长度4-3=1~

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rg register ll
string s[25];
ll ans,maxx,vis[25],n;
inline ll com(ll x,ll y)
{
    for(rg i=s[x].length()-1;i>=1;i--)
    {
        if(s[x][i]==s[y][0])
        {
            ll ans=0;
            for(rg j=i+1;j<=s[x].length()-1;j++)
            {
                if(s[x][j]!=s[y][++ans])return 0;
            }
            return s[y].length()-ans-1;
        }
    }
    return 0;
}
inline void dfs(ll x)
{
    for(rg i=1;i<=n;i++)
    {
        if(vis[i]<2&&com(x,i))
        {
            ans+=com(x,i);
            vis[i]++;
            dfs(i);//回溯
            vis[i]--;
            ans-=com(x,i);
        }
    }
    //cout<<ans<<endl;
    maxx=max(maxx,ans);
}
int main()
{
    cin>>n;
    for(rg i=1;i<=n;i++)cin>>s[i];
    getchar();
    char ch;
    cin>>ch;
    for(rg i=1;i<=n;i++)
    {
        if(s[i][0]==ch)
        {
            ans=s[i].length();
            vis[i]++;
            dfs(i);
            vis[i]--;
            maxx=max(maxx,ans);
            //cout<<maxx<<endl;
        }
    }
    cout<<maxx<<endl;
    //while(1)getchar();
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Educational Codeforces Round 81 (Rated for Div. 2) C.Obtain The String

    题意:串S,T,T是目标串,你需要将一个空串变成T,通过将S的任意子串添加到这个要变成T的串后头,这里的子串可以是不连续的,问最少次数,做不到就-1

    glm233
  • 牛客2019跨年AK场题解(一)

    找到了心仪的小姐姐月月后,华华很高兴的和她聊着天。然而月月的作业很多,不能继续陪华华聊天了。华华为了尽快和月月继续聊天,就提出帮她做一部分作业。 月月的其中一...

    glm233
  • 数学建模学习GM(1,1)灰色预测模型

    1.灰色系统的定义: 灰色系统指既含有已知信息又含有未知信息的系统。 2.灰色预测模型的定义: 对灰色系统进行预测的模型。 灰色模型(Grey ...

    glm233
  • dotnetcore 自动迁移工具

    捷义
  • 用 Charles 玩转微信小程序:抓取摩拜、OFO以及车来了数据

    最近沉迷于用 Charles 做代理抓手机的数据。 ? 关于如何使用 Charles 来做为手机的代理进行抓 HTTP/HTTPS 请求,这里有一篇非常详细的图...

    企鹅号小编
  • 牛牛的Link Power II

    时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 262144K,其他语言524288K 64bit IO Format: %lld 题目描述 牛...

    某些人
  • 站住,Maven依赖的scope作用域,还记得几个?

    在POM中,<dependency>引入了<scope>,它主要管理依赖的部署。目前<scope>可以使用5个值:

    程序员小明
  • React学习笔记—React组件

    小胖
  • 使用mockjs 随机生成模拟接口数据

    json-server模拟后端接口 https://cloud.tencent.com/developer/article/1541622

    王小婷
  • 站住,Maven依赖的scope作用域,还记得几个?

    在POM中,<dependency>引入了<scope>,它主要管理依赖的部署。目前<scope>可以使用5个值:

    乱敲代码

扫码关注云+社区

领取腾讯云代金券