1.E题：七段码

此题巨坑，反正题主走了弯路

1.思路分析：

数码管分为7段，要求的是数码管上不同的灯的亮灭组成是否是一个连通的线，我们需要把题目抽象为两个方面：

1. 利用dfs来求各种灯亮灭的所有组合。（子集问题）
2. 在一个子集中，利用并查集将所有的元素联通，最后遍历，如果有一个点与其他节点不连通，则该子集不可能是满足题目条件的结果之一

2.代码

2.1子集问题代码

//标准的回溯算法框架
static List<LinkedList<Integer>> res = new LinkedList<>();
static LinkedList<Integer> list = new LinkedList<Integer>();
public static void backTrack(int[] num, int start) {
  //子集问题的回溯条件很特别：没有特定的回溯条件，选择了一个元素以后就可以添加进结果集
        res.add(new LinkedList(list));
        for (int i = start; i < num.length; i++) {
            list.add(num[i]);
            backTrack(num, i + 1);        //添加下一个元素
            list.remove(list.size() - 1);
        }
    }

2.2并查集代码

public class UF{
    int count;
    int[] parent;
    int[] size;
    public UF(int n){
        this.count=n;
        parent=new int[n];
        size=new int[n];
        for(int i=0;i<n;i++){
            parent[i]=i;
            size[i]=1;
        }
    }
    public boolean isconnected(int p,int q){
        int rootp=find(p);
        int rootq=find(q);
        return rootp==rootq;
    }
    public int find(int node){
        while(parent[node]!=node){
            parent[node]=parent[parent[node]];
            node=parent[node];
        }
        return node;
    }
    public void union(int p,int q){
        int rootp=find(p);
        int rootq=find(q);
        if(isconnected(rootp,rootq)){
            return;
        }
        if(size[rootp]>size[rootq]){
            parent[rootq]=rootp;
            size[rootp]+=size[rootq];
        }else{
            parent[rootp]=rootq;
            size[rootq]+=size[rootp];
        }
        count--;
    }
    public int count(){
        return count;
    }
}

2.3完整代码

package com.lanqiao01;
import java.util.*;
public class Main {
    static List<LinkedList<Integer>> res = new LinkedList<>();
    static LinkedList<Integer> list = new LinkedList<Integer>();
    public static void main(String[] args) {
        int[] num = new int[]{1, 2, 3, 4, 5, 6, 7};
        int ans = 0;
        boolean flag = true;
        int[][] e = new int[8][8];
        e[1][2] = e[1][6] = 1;
        e[2][1] = e[2][7] = e[2][3] = 1;
        e[3][2] = e[3][7] = e[3][4] = 1;
        e[4][3] = e[4][5] = 1;
        e[5][7] = e[5][6] = e[5][4] = 1;
        e[6][5] = e[6][7] = e[6][1] = 1;
        e[7][2] = e[7][3] = e[7][5] = e[7][6] = 1;
//        UF uf = new UF(8);
//        for (int row = 1; row < 8; row++) {
//            for (int col = 1; col < 8; col++) {
//                if (e[row][col] == 1) {
////                    if (uf.isconnected(row, col)) {
////                        continue;
////                    }
//                    uf.union(row, col);
//                }
//            }
//        } // 完成并查集关系的建立
        //上面注释的代码不能加进去，因为一旦对邻接矩阵进行操作，所有的点都将被联通（对于任何一
        条边，可能只有两条或者三条边是联通的，但是对所有的边进行一次联通操作，那么所有的边
            都只会连接到一个父节点上）
        backTrack(num, 0);
        for (int i = 0; i < res.size(); i++) {
            UF uf = new UF(8);        
            //并查集的建立要在每次判断一个子结果是否符合题意之前，
            否则，如果不进行初始化重新创建，随着联通点的步步增加，所有的点又将重新被联通
            List<Integer> cur = res.get(i);
            if (cur.size() == 0) {
                continue;
            } else if (cur.size() == 1) {
                ans++;
            } else {
                for (int j = 0; j < cur.size(); j++) {
                    for (int k = j + 1; k < cur.size(); k++) {
                        int a = cur.get(j);
                        int b = cur.get(k);
                        if(e[a][b]==1){
                            uf.union(a,b);
                        }
                    }
                }
                int tmp=cur.get(0);
                for (int m=1;m<cur.size();m++){
                    if(!uf.isconnected(tmp,cur.get(m))){
                        flag=false;
                        break;
                    }
                    tmp=cur.get(m);
                }
                if (flag) {
                    ans++;
                }
                flag = true;
            }
        }
        // System.out.println(uf.isconnected(e[3][2], e[3][7]));
        System.out.println(ans);
        System.out.println(res);
        System.out.println(res.size());
    }
    public static void backTrack(int[] num, int start) {
        res.add(new LinkedList(list));
        for (int i = start; i < num.length; i++) {
            list.add(num[i]);
            backTrack(num, i + 1);
            list.remove(list.size() - 1);
        }
    }
}
class UF {
    int count;
    int[] parent;
    int[] size;
    public UF(int n) {
        this.count = n;
        // 初始化parent和size数组
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }
    public boolean isconnected(int p, int q) {
        int rootq = find(q);
        int rootp = find(p);
        return rootp == rootq;
    }
    public void union(int p, int q) {
        int rootp = find(p);
        int rootq = find(q);
        if (rootp == rootq) {
            return;
        }
        if (size[rootp] > size[rootq]) {
            parent[rootq] = rootp;
            size[rootp] += size[rootq];
        } else {
            parent[rootp] = rootq;
            size[rootq] += size[rootp];
        }
        count--;
    }
    public int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
    public int count() {
        return count;
    }
}

正确答案：80

2.作物杂交（dfs+dp）

• 输入

  6 2 4 6 5 3 4 6 4 9 1 2 1 2 3 1 3 4 2 3 5 4 5 6

• 输出

  16

1.思路分析

题目描述过于复杂，可能一开始并不能理解题目的意思。我们如何找杂交出最终作物的最少天数？
用动态规划的思路来说：设dp[T]（T表示目标作物）表示杂交出目标作物的最少天数，这个dp[T]包含两个部分，杂交出目标作物的时间+种子成熟的时间。
然后我们来明确初始值，根据题目我们可以知道我们刚开始拥有哪些种子，所以当我们杂交目标种子所需要的一部分种子是刚开始拥有的，那么我们等待的天数就是0；所以。
根据题意，我们可以知道杂交种子的方案，我们要在所有方案中找到一个天数最小的，那么大体思路就是暴力枚举，但是对于题目来说，暴力枚举的效率过低（两两种子都要枚举一遍，如果要经历多次的杂交，那么枚举的数量将成指数级增长）。所以核心思路是，反着枚举，即通过我们需要的目标种子来倒推我们需要的两个种子，再从我们需要的两个种子分别倒推出我们需要的另外两个种子。

2.代码

import java.util.*;
/*
    创建一个内部类Fangan表示哪两个种子能杂交出另一个种子
    首先获取输入，把我们拥有的种子标记为flag，dp[拥有的种子]=0;
    创建dfs函数，返回值是杂交出目标种子所需要的最小天数：
    如果该种子已拥有，返回dp[该种子]=0；
    如果该种子没有拥有，那么
    dp[该种子]=min(dp[该种子]，max(种子1成熟的时间，种子2成熟的时间）+max(dfs(种子1),dfs(种子2))
*/
public class Main {
    public static int n,m,k,t,min=Integer.MAX_VALUE,sum1=0;
    public static int[] time;
    public static int[] dp;
    public static List<Fangan>[] res;
    public static boolean[] flag;
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        n=scanner.nextInt();//n种种子
        m=scanner.nextInt();//已有的种子数量
        k=scanner.nextInt();//可杂交的方案数
        t=scanner.nextInt();//目标种子编号
        res=new LinkedList[2015];
        dp=new int[n+1];
        Arrays.fill(dp,99999);
        flag=new boolean[n+1];
        flag[0]=true;
        time=new int[n+1];
        for (int i = 1; i <= n; i++) {//时间
            time[i]=scanner.nextInt();
        }
        for (int i = 0; i < m; i++) {//已有的种子
            int tmp= scanner.nextInt();
            flag[tmp]=true;
            dp[tmp]=0;
        }
        for (int i = 0; i < res.length; i++) {//方案
            res[i]=new LinkedList<>();
        }
        for (int i=0;i<k;i++){
            int x= scanner.nextInt();
            int y= scanner.nextInt();
            int tmp= scanner.nextInt();
            res[tmp].add(new Fangan(x,y));
        }
        System.out.println(dfs(t));
    }
    public static int dfs(int mubiao) {
        if(flag[mubiao]){
            return dp[mubiao];
        }
        for (int i = 0; i < res[mubiao].size(); i++) {
            Fangan tmp=res[mubiao].get(i);
            dp[mubiao]=Math.min(dp[mubiao],Math.max(time[tmp.x],time[tmp.y])+Math.max(dfs(tmp.x),dfs(tmp.y)));
        }
        flag[mubiao]=true;
        return dp[mubiao];
    }
}
class Fangan{
    int x;
    int y;
    public Fangan(int x,int y) {
        // TODO Auto-generated constructor stub
        this.x=x;
        this.y=y;
    }
}