题目链接
记忆化搜索,直接dfs会爆三个点,用二进制存储状态
位运算计算
import java.util.*;
public class Main {
public static int n,res=0;
public static Map<Integer,List<Integer>> map=new HashMap<Integer,List<Integer>>();
public static String[] data=new String[17];
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
sc.nextLine();
for(int i=0;i<n;i++){
String s=sc.nextLine();
data[i]=s;
if(!map.containsKey((int)s.charAt(0))){
map.put((int)s.charAt(0),new ArrayList<Integer>());
}
if(!map.containsKey((int)s.charAt(s.length()-1))){
map.put((int)s.charAt(s.length()-1), new ArrayList<Integer>());
}
int temp=i;
map.get((int)s.charAt(0)).add(temp);
}
//System.out.println(map);
for(int i=0;i<n;i++){
res=Math.max(res,dfs(i,(1<<i)));
}
System.out.println(res);
}
public static int[][] is=new int[17][1<<16];
public static int dfs(int x,int y){
if(is[x][y]!=0)
return is[x][y];
int ans=0;
for(Integer next:map.get((int)data[x].charAt(data[x].length()-1))){
if(((y>>next)&1)==0){
ans=Math.max(ans,dfs(next,(y|(1<<next))));
}
}
return is[x][y]=ans+data[x].length();
}
}