美团8.15开发前四题AC代码，求第五题解法

求第五题解法，第五题憋了半小时没写出来，直接暴力感觉肯定过不了，纠结之中0AC。。。。

1. 逆序对，一共就四个数，偷鸡过了,代码就不贴了

2178 8712
21978 87912
219978 879912
2199978 8799912
21782178 87128712
21999978 87999912

2. 旅行，用栈暴力过，按照题目要求碰到start=end就算一次

import java.util.Scanner;

public class Solution2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        String start = null;
        int cnt = 0;
        for(int i = 0; i < n; i++){
            String[] record = sc.nextLine().split(" ");
            if(start == null){
                start = record[0];
            }else{
                if(start.equals(record[1])){
                    cnt ++;
                    start = null;
                }
            }
        }
        System.out.println(cnt);
    }
}

3. 送外卖，订单，并查集，当时时间紧，写的比较丑陋。。。

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Solutiin3 {
    private static void init(int parent[]){
        for(int i = 0; i < parent.length; i++){
            parent[i] = i;
        }
    }
    private static int findRoot(int x, int parent[]){
        if(x == parent[x]){
            return x;
        }else{
            parent[x] = findRoot(parent[x],parent);
            return parent[x];
        }
    }
    private static int unionNodes(int x, int y, int[] parent,int[] rank){
        int xRoot = findRoot(x,parent);
        int yRoot = findRoot(y,parent);
        if(xRoot == yRoot){
            return 0;
        }else{
            if(rank[xRoot] > rank[yRoot]){
                parent[yRoot] = xRoot;
            }else if(rank[yRoot] > rank[xRoot]){
                parent[xRoot] = yRoot;
            }else{
                parent[xRoot] = yRoot;
                rank[yRoot]++;
            }
            //parent[xRoot] = yRoot;
            return 1;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        scanner.nextLine();
        int[] parent = new int[n + 1];
        int[] rank = new int[n + 1];
        init(parent);
        for(int i = 0; i < m; i++){
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            scanner.nextLine();
            unionNodes(a, b, parent, rank);
        }
        boolean[] used = new boolean[n + 1];
        List<List<Integer>> res = new ArrayList<>();
        for(int i = 1; i <= n; i++){
            if(used[i]){
                continue;
            }
            List<Integer> tmp = new ArrayList<>();
            for(int j = i; j <= n; j++){
                if(!used[j]){
                    if(findRoot(i, parent) == findRoot(j, parent)){
                        tmp.add(j);
                        used[j] = true;
                    }
                }
            }
            res.add(tmp);
        }
        System.out.println(res.size());
        for(List<Integer> list : res){
            for(int a : list){
                System.out.print(a + " ");
            }
            System.out.println();
        }

    }
}

4. 动态规划，稍微优化了一下循环条件AC了

import java.util.Scanner;
public class Solution4 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a = sc.nextInt();
        int b = sc.nextInt();
        sc.nextLine();
        int[][] vals = new int[n][2];
        int[][] dp = new int[a + 1][b + 1];
        for(int i = 1; i <= n; i++){
            vals[i - 1][0] = sc.nextInt();
            vals[i - 1][1] = sc.nextInt();
            sc.nextLine();
            for(int j = Math.min(a, i); j >= 0; j--){
                for(int k = Math.min(b, i); k >= 0; k--){
                    if(j + k + (n - i + 1) < a + b){
                        break;
                    }
                    //dp[j][k] = dp[j][k];
                    if(j > 0)
                        dp[j][k] = Math.max(dp[j][k], dp[j - 1][k] + vals[i - 1][0]);
                    if(k > 0)
                        dp[j][k] = Math.max(dp[j][k], dp[j][k - 1] + vals[i - 1][1]);
                }
            }
        }
        System.out.println(dp[a][b]);
    }
}