acwing1117. 单词接龙(深搜dfs)[通俗易懂]

acwing1117. 单词接龙(深搜dfs)[通俗易懂]单词接龙是一个与我们经常玩的成语接龙相类似的游戏。现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”,每个单词最多被使用两次。在两个单词相连时,其重合部分合为一部分,例如 beast 和 astonish ,如果接成一条龙则变为 beastonish。我们可以任意选择重合部分的长度,但其长度必须大于等于1,且严格小于两个串的长度,例如 at 和 atide 间不能相连。输入格式输入的第一行为一个单独的整数 n 表示单词数,以下 n 行每行有一个单词(只含有大写或小写字母

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

单词接龙是一个与我们经常玩的成语接龙相类似的游戏。

现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”,每个单词最多被使用两次。

在两个单词相连时,其重合部分合为一部分,例如 beast 和 astonish ,如果接成一条龙则变为 beastonish。

我们可以任意选择重合部分的长度,但其长度必须大于等于1,且严格小于两个串的长度,例如 at 和 atide 间不能相连。

输入格式
输入的第一行为一个单独的整数 n 表示单词数,以下 n 行每行有一个单词(只含有大写或小写字母,长度不超过20),输入的最后一行为一个单个字符,表示“龙”开头的字母。

你可以假定以此字母开头的“龙”一定存在。

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

数据范围
n≤20

输入样例:
5
at
touch
cheat
choose
tact
a
输出样例:
23

提示
连成的“龙”为 atoucheatactactouchoose。

题解
深搜dfs

#include<bits/stdc++.h>
using namespace std;
int n;
const int N = 1e2 + 10;
string word[N];
const int INF = 0x3f3f3f3f;
int res = 0;
vector<int>edge[N];
int g[N][N],num[N];
void dfs(int len,int id){ 
   
    res = max(res,len);
    for(auto &a : edge[id]){ 
   
        if(num[a] != 2){ 
   
            num[a] ++;
            dfs(len + word[a].size() - g[id][a],a);
            num[a] --;
        }
    }
}
int main(){ 
   
    char x;
    cin>>n;
    for(int i = 0;i < n;i ++){ 
   
        cin>>word[i];
    }
    cin>>x;
    for(int i = 0;i < n;i ++){ 
   
        for(int j = 0;j < n;j ++){ 
   
            for(int k = 1;k < min(word[i].size(),word[j].size());k ++){ 
   
                if(word[i].substr(word[i].size() - k) == word[j].substr(0,k)){ 
   
                    g[i][j] = k;
                    edge[i].push_back(j);
                    break;
                }
            }
        }
    }
    for(int i = 0;i < n;i ++){ 
   
        if(word[i][0] == x)edge[n].push_back(i),g[n][i] = 1;
    }
    dfs(1,n);
    cout<<res<<endl;
    return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168667.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • printwriter Java,java PrintWriter无法解析

    printwriter Java,java PrintWriter无法解析IhavenoideawhyIgetthemessage”cannotberesolved”onoutineclipseonthe11thlineimportjava.io.*;publicclassdriver{publicstaticvoidmain(String[]args){try{PrintWriterout=newPri…

  • phpstorm2021激活码【2021免费激活】

    (phpstorm2021激活码)JetBrains旗下有多款编译器工具(如:IntelliJ、WebStorm、PyCharm等)在各编程领域几乎都占据了垄断地位。建立在开源IntelliJ平台之上,过去15年以来,JetBrains一直在不断发展和完善这个平台。这个平台可以针对您的开发工作流进行微调并且能够提供…

  • TLSF内存分配器记录[通俗易懂]

    TLSF内存分配器记录[通俗易懂]论文:《TLSF:aNewDynamicMemoryAllocatorforReal-TimeSystems》这也是Unity底层使用的内存分配器。我直接从论文中间部分开始看。firstlevel存的是每个内存分配大小,从2的四次方到2的31次方。而对应每个大小,又指向一个二级列表,里面被分成4级,每一级的范围认为是同一类。1表示空闲,所以只有2的六次方和2的15次方块是空闲的。再看它指向的二级列表。只有2的六次方+16到2的6次方+32的这个.

  • MySQLdump的参数详解大全

    MySQLdump的参数详解大全

  • Mac拷贝/复制文件夹路径快捷键

    Mac拷贝/复制文件夹路径快捷键

  • top命令查看内存信息_ubuntu查看cpu信息

    top命令查看内存信息_ubuntu查看cpu信息top命令是Linux下常用的性能分析工具,能够实时显示系统中各个进程的资源占用状况,类似于Windows的任务管理器。top显示系统当前的进程和其他状况,是一个动态显示过程,即可以通过用户按键来不断刷新当前状态.如果在前台执行该命令,它将独占前台,直到用户终止该程序为止.比较准确的说,top命令提供了实时的对系统处理器的状态监视.它将显示系统中CPU最“敏感”的任务列表.该命令可以按CPU使…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号