洛谷 单词接龙 dfs 字符串处理
🍑 NOIP2000 提高组 单词接龙
题目背景
注意:本题为上古 NOIP 原题,不保证存在靠谱的做法能通过该数据范围下的所有数据。
题目描述
单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”(每个单词都最多在“龙”中出现两次),在两个单词相连时,其重合部分合为一部分,例如 beast
和 astonish
,如果接成一条龙则变为 beastonish
,另外相邻的两部分不能存在包含关系,例如 at
和 atide
间不能相连。
输入格式
输入的第一行为一个单独的整数 n n n 表示单词数,以下 n n n 行每行有一个单词,输入的最后一行为一个单个字符,表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在。
输出格式
只需输出以此字母开头的最长的“龙”的长度。
样例 #1
样例输入 #1
5
at
touch
cheat
choose
tact
a
样例输出 #1
23
提示
样例解释:连成的“龙”为 atoucheatactactouchoose
。
n ≤ 20 n \le 20 n≤20。
🍑 AC code
import java.util.*;
public class Main
{
static int N = 30, n;
static String[] ss = new String[N];
// g[i][j] 记录单词i和单词j 的后缀前缀最短匹配长度(0表示不匹配)
static int[][] g = new int[N][N];
static int[] cnt = new int[N];// 记录单词的使用次数
static int ans;// 记录答案
// s 表示当前的字符串,id末尾单词的编号
static void dfs(String s, int id)
{
ans = Math.max(ans, s.length());
cnt[id] ;
for (int i = 0; i < n; i )
if (g[id][i] != 0 && cnt[i] < 2)
{
dfs(s ss[i].substring(g[id][i]), i);
}
cnt[id]--;
}
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for (int i = 0; i < n; i )
ss[i] = sc.next();
char start = sc.next().charAt(0);
// 预处理边(求最小前后缀匹配长度)
for (int i = 0; i < n; i )
for (int j = 0; j < n; j )
{
String a = ss[i];
String b = ss[j];
int len = Math.min(a.length(), b.length());
for (int k = 1; k < len; k )
if (a.substring(a.length() - k).equals(b.substring(0, k)))
{
g[i][j] = k;
break;
}
}
// 枚举每一个单词
for (int i = 0; i < n; i )
{
if (ss[i].charAt(0) == start)
dfs(ss[i], i);
}
System.out.println(ans);
}
}
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhfeabab
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01