头像

钟意




离线:12小时前



钟意
12小时前
    private static class Pet {
        private int number;
        private int power;

        public Pet(int number, int power) {
            this.number = number;
            this.power = power;
        }
    }

    public static void main(String[] args) {
        int number = in.nextInt();
        int power = in.nextInt();
        int n = in.nextInt();
        Pet[] pets = new Pet[n + 1];
        int[][] dp = new int[number + 1][power + 1];
        for (int i = 1; i < n + 1; i++) pets[i] = new Pet(in.nextInt(), in.nextInt());
        for (int i = 1; i < n + 1; i++) {
            for (int j = number; j >= pets[i].number; j--) {
                for (int k = power - 1; k >= pets[i].power; k--) {
                    dp[j][k] = Math.max(dp[j][k], dp[j - pets[i].number][k - pets[i].power] + 1);
                }
            }
        }
        int num = dp[number][power - 1];
        int res = power - 1;
        for (int i = power - 1; i >= 0; i--) {
            if (num == dp[number][i]) res = i;
            else break;
        }
        out.println(num + " " + (power - res));
        out.flush();
        out.close();
    }


活动打卡代码 AcWing 1024. 装箱问题

钟意
12小时前
    public static void main(String[] args) {
        int m = in.nextInt();
        int n = in.nextInt();
        int[] arr = new int[n + 1];
        int[] dp = new int[m + 1];
        for (int i = 1; i < n + 1; i++) arr[i] = in.nextInt();
        for (int i = 1; i < n + 1; i++) {
            for (int j = m; j >= arr[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - arr[i]] + arr[i]);
            }
        }
        out.println(m - dp[m]);
        out.flush();
        out.close();
    }



活动打卡代码 AcWing 423. 采药

钟意
13小时前
    private static class Herb{
        private int time;
        private int value;

        public Herb(int time, int value) {
            this.time = time;
            this.value = value;
        }
    }
    public static void main(String[] args) {
//        function1();
        function2();
    }
    private static void function2() {
        int t = in.nextInt();
        int n = in.nextInt();
        Herb[] herbs = new Herb[n + 1];
        for (int i = 1; i <= n; i++) {
            herbs[i] = new Herb(in.nextInt(), in.nextInt());
        }
        int[] dp = new int[t + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = t; j >= herbs[i].time; j--) {
                dp[j] = Math.max(dp[j], dp[j - herbs[i].time] + herbs[i].value);
            }
        }
        out.println(dp[t]);
        out.flush();
        out.close();
    }



钟意
5天前

朴素写法:

    private static void function1() {
        int n = in.nextInt();
        int m = in.nextInt();
        Goods[] gs = new Goods[n + 1];
        for (int i = 1; i < n + 1; i++) gs[i] = new Goods(in.nextInt(), in.nextInt(), in.nextInt());
        int[][] dp = new int[n + 1][m + 1];
//        int[][] last = new int[n + 1][m + 1];
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 1; i < n + 1; i++) {
            int v = gs[i].volume;
            int w = gs[i].weight;
            int number = gs[i].number;
            //r : remainder
            for (int r = 0; r < v; r++) {
                list.clear();
                for (int k = 0; r + k * v <= m; k++) {
                    if (!list.isEmpty() && k - list.getFirst() > number) list.removeFirst();
                    while (!list.isEmpty() &&
                            dp[i - 1][r + k * v] - k * w >=
                                    dp[i - 1][r + list.getLast() * v] - list.getLast() * w
                    ) {
                        list.removeLast();
                    }
                    list.add(k);
                    dp[i][r + k * v] = dp[i - 1][r + list.getFirst() * v] + ((k - list.getFirst()) * w);
                }
            }
        }
        out.println(dp[n][m]);
        out.flush();
        out.close();
    }

空间优化写法:

    private static void function2() {
        int n = in.nextInt();
        int m = in.nextInt();
        Goods[] gs = new Goods[n + 1];
        for (int i = 1; i < n + 1; i++) gs[i] = new Goods(in.nextInt(), in.nextInt(), in.nextInt());
        int[] dp = new int[m + 1];
        int[] bak = new int[m + 1];
//        int[][] last = new int[n + 1][m + 1];
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 1; i < n + 1; i++) {
            System.arraycopy(dp, 0, bak, 0, m + 1);
            int v = gs[i].volume;
            int w = gs[i].weight;
            int number = gs[i].number;
            //r : remainder
            for (int r = 0; r < v; r++) {
                list.clear();
                for (int k = 0; r + k * v <= m; k++) {
                    if (!list.isEmpty() && k - list.getFirst() > number) list.removeFirst();
                    while (!list.isEmpty() &&
                            bak[r + k * v] - k * w >=
                                    bak[r + list.getLast() * v] - list.getLast() * w
                    ) {
                        list.removeLast();
                    }
                    list.add(k);
                    dp[r + k * v] = bak[r + list.getFirst() * v] + ((k - list.getFirst()) * w);
                }
            }
        }
        out.println(dp[m]);
        out.flush();
        out.close();
    }




钟意
5天前

题目思路

$$
f(i,j):所有由A串前i个元素和B串前j个元素且以b_j结尾元素组成的公共上升子序列的最大长度
$$

$$
集合按照是否包含a_i元素分为:
$$

$$
f(i-1,j):一定不包含a_i元素的公共上升子序列\tag1
$$

$$
一定包含a_i元素,因为是公共子序列所以一定需要满足a_i=b_j
$$

$$
max(f(i-1,k)+1)(1<=k<j\& b_k<a_i)\tag2
$$

$$
找到所有由A串前i-1个元素和B串前k个元素且以b_k结尾元素组成的公共上升子序列的最大长度,加上a_i,b_j这一对的长度
$$

$$
f(i,j)=max((1),(2))
$$

朴素写法:

    public static void main(String[] args) {
        int n = in.nextInt();
        int[] a = new int[n + 1];
        int[] b = new int[n + 1];
        int[][] dp = new int[n + 1][n + 1];
        for (int i = 1; i < n + 1; i++) a[i] = in.nextInt();
        for (int i = 1; i < n + 1; i++) b[i] = in.nextInt();
        int res = 0;
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                dp[i][j] = dp[i - 1][j];
                if (a[i] == b[j]) {
                    dp[i][j] = Math.max(dp[i][j], 1);
                    for (int k = 1; k < j; k++) {
                        if (b[k] < b[j])
                            dp[i][j] = Math.max(dp[i][j], dp[i - 1][k] + 1);
                    }
                }
                res = Math.max(res, dp[i][j]);
            }
        }
        out.println(res);
        out.flush();
        out.close();
    }

优化写法:
$$
因为a_i=b_j,将其替换发现
$$

$$
每次循环求得的max是满足a_i > b_k的f(i - 1,k)的前缀最大值
$$

$$
因此可以直接将max提到第一层循环外面,减少重复计算,此时只剩下两重循环。
$$

    private static int functino2() {
        int n = in.nextInt();
        int[] a = new int[n + 1];
        int[] b = new int[n + 1];
        int[][] dp = new int[n + 1][n + 1];
        for (int i = 1; i < n + 1; i++) a[i] = in.nextInt();
        for (int i = 1; i < n + 1; i++) b[i] = in.nextInt();
        int res = 0;
        int max;
        for (int i = 1; i < n + 1; i++) {
            max = 0;
            for (int j = 1; j < n + 1; j++) {
                dp[i][j] = dp[i - 1][j];
                if (a[i] == b[j]) dp[i][j] = Math.max(dp[i][j], max + 1);
                if (a[i] > b[j]) max = Math.max(max, dp[i - 1][j]);
                res = Math.max(res, dp[i][j]);
            }
        }
        return res;
    }



活动打卡代码 AcWing 187. 导弹防御系统

钟意
5天前
    private static List<Integer> upSystem = new ArrayList<>();
    private static List<Integer> downSystem = new ArrayList<>();
    private static int res;
    private static int[] arr;
    private static void dfs(int total, int upNumber, int downNumber, int cur) {
        if (res <= upNumber + downNumber) return;
        if (total == cur) {
            res = upNumber + downNumber;
            return;
        }
        int k = -1;
        for (int i = 0; i < upSystem.size(); i++) {
            if (arr[upSystem.get(i)] > arr[cur]) {
                k = i;
                break;
            }
        }
        //搜放在up system的情况
        if (k == -1) {
            upSystem.add(cur);
            dfs(total, upNumber + 1, downNumber, cur + 1);
            upSystem.remove(upSystem.size() - 1);
        }else {
            int temp = upSystem.get(k);
            upSystem.set(k, cur);
            dfs(total, upNumber, downNumber, cur + 1);
            upSystem.set(k, temp);
        }

        k = -1;
        for (int i = 0; i < downSystem.size(); i++) {
            if (arr[downSystem.get(i)] < arr[cur]) {
                k = i;
                break;
            }
        }
        //搜放在down system的情况
        if (k == -1) {
            downSystem.add(cur);
            dfs(total, upNumber, downNumber + 1, cur + 1);
            downSystem.remove(downSystem.size() - 1);
        }else {
            int temp = downSystem.get(k);
            downSystem.set(k, cur);
            dfs(total, upNumber, downNumber, cur + 1);
            downSystem.set(k, temp);
        }
    }



钟意
5天前
    public static void main(String[] args) {
        int n = in.nextInt();
        int[] arr = new int[n + 1];
        int[] dp = new int[n + 1];
        for (int i = 1; i < n + 1; i++) {
            arr[i] = in.nextInt();
        }
        int res = 0;
        for (int i = 1; i < n + 1; i++) {
            dp[i] = 1;
            for (int j = 1; j < n + 1; j++) {
                if (arr[j] < arr[i])
                    dp[i] = Math.max(dp[i], dp[j] + arr[i]);
            }
            res = Math.max(res, dp[i]);
        }
        out.println(res);
        out.flush();
        out.close();
    }


活动打卡代码 AcWing 1012. 友好城市

钟意
5天前
    private static class City{
        private int a;
        private int b;

        public City(int a, int b) {
            this.a = a;
            this.b = b;
        }
    }
    public static void main(String[] args) {
        int n = in.nextInt();
        int[] dp = new int[n + 1];
        City[] cities = new City[n];
        for (int i = 0; i < n; i++) {
            cities[i] = new City(in.nextInt(), in.nextInt());
        }
        Arrays.sort(cities, Comparator.comparingInt(a -> a.a));
        int res = 0;
        for (int i = 1; i <= n; i++) {
            dp[i] = 1;
            for (int j = 1; j < i; j++) {
                if (cities[j - 1].b < cities[i - 1].b) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            res = Math.max(res, dp[i]);
        }
        out.println(res);
        out.flush();
        out.close();
    }



活动打卡代码 AcWing 1010. 拦截导弹

钟意
5天前
    public static void main(String[] args) {
        String s = in.nextLine();
        String[] ss = s.split(" ");
        int n = ss.length;
        int[] arr = new int[n + 1];
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) arr[i] = Integer.parseInt(ss[i - 1]);
        int res1 = 0;
        for (int i = 1; i <= n; i++) {
            dp[i] = 1;
            for (int j = 1; j < i; j++) {
                if (arr[j] >= arr[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            res1 = Math.max(res1, dp[i]);
        }

        // store index
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            int k = -1;
            for (int j = 0; j < list.size(); j++) {
                if (arr[list.get(j)] >= arr[i]) {
                    k = j;
                    break;
                }
            }
            if (k == -1) list.add(i);
            else list.set(k, i);
        }
        int res2 = list.size();
        out.println(res1);
        out.println(res2);
        out.flush();
        out.close();
    }



活动打卡代码 AcWing 482. 合唱队形

钟意
5天前
    public static void main(String[] args) {
        int n = in.nextInt();
        int[] arr = new int[n + 1];
        int[] leftToRightDp = new int[n + 1];
        int[] rightToLeftDp = new int[n + 1];
        for (int i = 1; i <= n; i++) arr[i] = in.nextInt();
        for (int i = 1; i <= n; i++) {
            leftToRightDp[i] = 1;
            for (int j = 1; j < i; j++) {
                if (arr[j] < arr[i]) {
                    leftToRightDp[i] = Math.max(leftToRightDp[i], leftToRightDp[j] + 1);
                }
            }
        }
        for (int i = n; i >= 1; i--) {
            rightToLeftDp[i] = 1;
            for (int j = n; j > i; j--) {
                if (arr[j] < arr[i]) {
                    rightToLeftDp[i] = Math.max(rightToLeftDp[i], rightToLeftDp[j] + 1);
                }
            }
        }
        int res = 0;
        for (int i = 1; i < n + 1; i++) res = Math.max(res, leftToRightDp[i] + rightToLeftDp[i] - 1);
        out.println(n - res);
        out.flush();
        out.close();
    }