锐客网

  1. 首页 > it技术 > >

P1019 单词接龙（dfs，洛谷，java）

【P1019 单词接龙（dfs，洛谷，java）】洛谷链接：https://www.luogu.com.cn/problem/P1019
P1019 单词接龙（dfs，洛谷，java）
文章图片

P1019 单词接龙（dfs，洛谷，java）
文章图片

import java.util.Scanner; public class Main { static int n=0; //单词数 static char ch; //开头字母 static String[] str=new String[30]; //储存字符串 static int[][] yc=new int[30][30]; //两个字母的最小重叠部分 static int[] vis=new int[30]; //判断单词使用频率 //mt函数，返回x单词后连接一个y单词的最小重叠部分 public static int mt(int x,int y) { boolean pp=true; int ky=0; for(int k=str[x].length()-1; k>=0; k--) { //从x单词尾部向前看看最小重叠部分是从哪里开始的，以为因为是倒着来，所以保证是最小的 for(int kx=k; kx[x].length(); kx++) { if(str[x].charAt(kx)!=str[y].charAt(ky++)) { pp=false; break; } } if(pp==true) { //如果说当前以k为开头的前一个单词后缀 ,是后面单词的前缀，就马上返回重叠部分。（tr[x].size()-k是找出来的规律） return str[x].length()-k; } //重置 ky=0; pp=true; } return 0; } static int ans=-1; //答案 static int an=0; //每次搜到的当前最长串 //p为尾部单词编号(p的后缀就是“龙”的后缀，因为p已经连接到”龙“后面了) public static void dfs(int p) { boolean jx=false; for(int j=1; j<=n; j++) { if(vis[j]>=2) continue; //使用了两次就跳过 if(yc[p][j]==0) continue; //两单词之间没有重合部分就跳过 if(yc[p][j]==str[p].length()||yc[p][j]==str[j].length()) { //两者存在包含关系就跳过 continue; } an+=str[j].length()-yc[p][j]; //两单词合并再减去最小重合部分 vis[j]++; //使用了一次 jx=true; //标记一下当前已经成功匹配到一个可以连接的部分 dfs(j); //接上去 an-=str[j].length()-yc[p][j]; //回溯，就要再减回去那一部分长度 vis[j]--; //回溯,使用-- } if(jx==false) { ans=Math.max(ans,an); } return; } public static void main(String[] args) { Scanner in=new Scanner(System.in); //输入 n=in.nextInt(); for(int i=1; i<=n; i++) { str[i]=in.next(); } ch=in.next().charAt(0); //预处理yc数组。yc[i][j]就表示，i单词后连接一个j单词的最小重叠部分 //比如 i表示at,j表示att. yc[i][j]就为2 但是yc[j][i]就为0. //预处理是一个关键 for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { yc[i][j]=mt(i,j); } }for(int i=1; i<=n; i++) {//从头到尾看一下有没有以指定开头字母为开头的单词 if(str[i].charAt(0)==ch) {//如果有，就以当前单词为基准进行搜索。 vis[i]++; //使用过一次 an=str[i].length(); //更新当前串长度 dfs(i); //接上 vis[i]=0; //消除影响 } }System.out.println(ans); } }

    推荐阅读


    上一篇：架构项目|vue报错（TypeError: Object(...) is not a function）

    下一篇：python字符串与编码之间的转换