本文主要是介绍HDU 1560 IDA*，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给出ｎ个串，求最短公共串（不要求连续）
h ，最少还需要多长来匹配所有。
import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.StringTokenizer;public class Main {public static void main(String[] args) {new HDU1560().solve();}
}class HDU1560{InputReader in = new InputReader(System.in) ;PrintWriter out = new PrintWriter(System.out) ;final String ACGT = "ACGT" ;final int N = 10 ;int[][] val = new int[N][N] ;int[] len = new int[N] ;int n ;void solve(){int t = in.nextInt() ;while(t-- > 0){n = in.nextInt() ;int pos = 0 ;for(int i = 0 ; i < n ; i++){String s = in.next() ;len[i] = s.length() ;pos = Math.max(pos , len[i]) ;for(int j = 0 ; j < len[i] ; j++) val[i][j] = ACGT.indexOf(s.charAt(j)) ;}int[] idx = new int[N] ;Arrays.fill(idx , 0) ;for( ; ! dfs(pos, idx) ; pos++) ;out.println(pos) ;}out.flush() ; }int getH(int[] idx){int[] max = new int[4] ;int[] c = new int[4] ;Arrays.fill(max , 0) ;for(int i = 0 ; i < n ; i++){Arrays.fill(c , 0) ;for(int j = idx[i] ; j < len[i] ; j++)c[val[i][j]]++ ;for(int j = 0 ; j < 4 ; j++)max[j] = Math.max(max[j] , c[j]) ;}return max[0] + max[1] + max[2] + max[3] ;}boolean dfs(int pos , int[] idx){int h = getH(idx) ;if(h > pos) return false ;if(h == 0) return true ;if(pos == 0) return true ;int[] nextIdx = new int[N] ;for(int i = 0 ; i < 4 ; i++){for(int j = 0 ; j < n ; j++){if(idx[j] < len[j] && i == val[j][idx[j]])nextIdx[j] = idx[j] + 1 ;else nextIdx[j] = idx[j] ;}if(dfs(pos-1 , nextIdx)) return true ;}return false ;}}class InputReader {public BufferedReader reader;public StringTokenizer tokenizer;public InputReader(InputStream stream) {reader = new BufferedReader(new InputStreamReader(stream), 32768);tokenizer = new StringTokenizer("");}private void eat(String s) {tokenizer = new StringTokenizer(s);}public String nextLine() {try {return reader.readLine();} catch (Exception e) {return null;}}public boolean hasNext() {while (!tokenizer.hasMoreTokens()) {String s = nextLine();if (s == null)return false;eat(s);}return true;}public String next() {hasNext();return tokenizer.nextToken();}public int nextInt() {return Integer.parseInt(next());}public long nextLong() {return Long.parseLong(next());}public double nextDouble() {return Double.parseDouble(next());}public BigInteger nextBigInteger() {return new BigInteger(next());}}
这篇关于HDU 1560 IDA*的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
