POJ1699-DNA

笔者解析

  1. 本题使用预处理路径增加长度的办法来解题

    具体为：设立一个二维数组，来存取i，j字符顺序排列下

    ​ 算出i，j的长度的重叠部分，然后再用j - 重叠部分算出所需要增加的长度

  2. 使用DFS来深度搜索最小值

笔者代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
import java.util.Scanner;

public class Main {

    public static int [][] arr;
    public static String [] d;
    static int[] visit ;
    static int minLen,all=0;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        //输入计算次数
        int m = scanner.nextInt();
        int n ;
        while(m-->0){
            //输入片段数量
            n = scanner.nextInt();
            //创建二维数组保存两者之间的重叠区域字母数量
             arr = new int[n][n];
             //创建一维数组，保存每个字符串
             d = new String[n];
             visit = new int[n];
            //输入DNA片段数据
            for (int i = 0; i < n; i++) {
                d[i] = scanner.next();
                all+=d[i].length();
            }
            //初始化arr中的数据，列举出每一个数据
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {

                    //当数据自我重叠时跳过
                    if(i == j){
                        //System.out.print(arr[i][j]+ " ")
                        ;continue;}
                    //初始化片段值增加值
                    add(i,j);
                    //System.out.print( arr[i][j]+ " ");
                }
               // System.out.println();
            }

            //初始化最优解
            minLen = all+1;
            //使用DFS爆搜剪枝
            for (int i = 0; i < n; i++) {
                visit[i] = 1;
                DFS(n,1,d[i].length(),i);
                visit[i] = 0;
            }
            System.out.println(minLen);
        }
    }


    //初始化压缩数据函数

    static void add(int i,int j){
        //选取较小长度为当前的长度限制
        int len = Math.min(d[i].length(),d[j].length());
        for (int k = len; k >= 0; k--) {
            int h = 0;
            for(;h<k;h++){
                //当匹配
                if (d[i].charAt(d[i].length()-k+h)!=d[j].charAt(h)){
                    break;
                }
            }
            if(h == k){
                arr[i][j] = d[j].length()-k;
                break;
            }
        }
    }
    //爆搜剪枝计算最短长度,n为总个数，m为使用个数，len为当前长度,now为上一个的下标

    public static void DFS(int n,int m,int len,int now){
        //当当前值已经大于等于已经得到的最小值，则进行剪枝
        if(len>minLen){return;}
        if(n == m){
            minLen =Math.min(len,minLen);
            return;
        }

        for (int i = 0; i < n; i++) {
            if(visit[i] == 0){
                visit[i] = 1;
                DFS(n,m+1,len+arr[now][i],i);
                visit[i] = 0;
            }
        }
    }
}