头像

Sei




离线:16天前


最近来访(4)
用户头像
zombotany
用户头像
乌搏猿

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

Sei
8个月前
import java.util.*;
public class Main {

     public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] num = new int[n];
        for (int i = 0; i < n; i++) {
            num[i] = sc.nextInt();
        }

        int res = 0;
        for (int i = 0; i <= n; i++) {
            int[] a = Arrays.copyOfRange(num, 0, i), b = Arrays.copyOfRange(num, i, n);

            res = Math.max(res, lis(a) + lis2(b));
        }

        System.out.println(n - res);
    }

    public static int lis(int[] num){
        if(num.length == 0){
            return 0;
        }
        int[] dp = new int[num.length];
        int res = 0;
        dp[0] = 1;
        for (int i = 1; i < num.length; i++) {
            for (int j = 0; j < i; j++) {
                if(num[i] > num[j]){
                    dp[i] = Math.max(dp[i], dp[j]);
                }
            }
            dp[i] = dp[i] + 1;
            res = Math.max(res, dp[i]);
        }
        return res;
    }

    public static int lis2(int[] num){
        if(num.length == 0){
            return 0;
        }
        int[] dp = new int[num.length];
        int res = 0;
        dp[0] = 1;
        for (int i = 1; i < num.length; i++) {
            for (int j = 0; j < i; j++) {
                if(num[i] < num[j]){
                    dp[i] = Math.max(dp[i], dp[j]);
                }
            }
            dp[i] = dp[i] + 1;
            res = Math.max(res, dp[i]);
        }
        return res;
    }

}



活动打卡代码 AcWing 1603. 整数集合划分

Sei
8个月前
import java.util.*;
public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int[] n = new int[N];
        int sum = 0;
        for (int i = 0; i < N; i++) {
            n[i] = scanner.nextInt();
            sum += n[i];
        }
        Arrays.sort(n);
        int s = 0;
        for (int i = 0; i < N / 2; i++) {
            s += n[i];
        }
        System.out.print(N % 2==0? 0 : 1);
        System.out.print(" " + (sum - 2*s));
    }

}


活动打卡代码 AcWing 1371. 货币系统

Sei
8个月前
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt(), N = scanner.nextInt();
        int[] coins = new int[size];
        long[] dp = new long[N + 1];
        for (int i = 0; i < size; i++) {
            coins[i] = scanner.nextInt();
        }
        dp[0] = 1;
        for (int i = 0; i < size; i++) {
            for (int j = coins[i]; j <= N; j++) {
                dp[j] += dp[j - coins[i]];
            }
        }
        System.out.println(dp[N]);
    }
}



活动打卡代码 AcWing 754. 平方矩阵 II

Sei
8个月前
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        while(n != 0){

            int[][] m = new int[n][n];
            int tmp = 1;
            for (int i = 0; i < n; i++) {
                for (int j = i; j < n; j++) {
                    m[i][j] = tmp;
                    tmp ++;
                }
                tmp = 1;
            }

            for (int i = n-1; i >= 0; i--) {
                for (int j = 0; j < i; j++) {
                    m[i][j] = m[j][i];
                }
            }

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    System.out.print(m[i][j] + " ");
                    if(j == n - 1){
                        System.out.print("\n\r");
                    }
                }
            }
            System.out.println();
            n = scanner.nextInt();
        }
    }

}



活动打卡代码 AcWing 1532. 找硬币

Sei
9个月前
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt(), target = scanner.nextInt();
        int[] coin = new int[size];
        for (int i = 0; i < size; i++) {
            coin[i] = scanner.nextInt();
        }

        Set<Integer> set = new HashSet<>();
        int v1 = Integer.MAX_VALUE, v2 = Integer.MIN_VALUE, min, max;
        for (int i : coin) {
            if(set.contains(target - i)){
                min = Math.min(i, target - i); max = Math.max(i, target - i);
                v1 = Math.min(v1, min); v2 = Math.max(v2, max);
            }
            set.add(i);
        }
        if(v1 == Integer.MAX_VALUE){
            System.out.println("No Solution");
        }else{
            System.out.println(v1 + " " + v2);
        }
    }
}



活动打卡代码 AcWing 1208. 翻硬币

Sei
9个月前
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String source = scanner.next(), target = scanner.next();
        char[] s = source.toCharArray(), t = target.toCharArray();
        int res = 0;
        for (int i = 0; i < s.length-1; i++) {
            if(s[i] != t[i]){
                swap(s, i);
                swap(s, i+1);
                res ++;
            }
        }
        System.out.println(res);
    }

    private static void swap(char[] c, int i){
        if(c[i] == 'o'){
            c[i] = '*';
        }else{
            c[i] = 'o';
        }
    }
}



活动打卡代码 AcWing 756. 蛇形矩阵

Sei
9个月前
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        int n, m;
        try(Scanner sc = new Scanner(System.in)){
            m = sc.nextInt(); n = sc.nextInt();
        }
        int[] dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0};
        int[][] res = new int[m][n];
        int x = 0, y = 0, d = 0, a, b;
        for (int i = 0; i < m * n; i++) {
            res[x][y] = i + 1;
            a = x + dx[d]; b = y + dy[d];
            if (a < 0 || a >= m || b < 0 || b>= n || res[a][b]!=0) {
                d = (d+1)%4;
                a = x + dx[d]; b = y + dy[d];
            }
            x = a; y = b;
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(res[i][j]);
                if(j != n-1){
                    System.out.print(" ");
                }
            }
            System.out.print("\r\n");
        }
    }
}


活动打卡代码 AcWing 429. 奖学金

Sei
9个月前
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        final int L, n;
        int[][] scores;
        try(Scanner sc = new Scanner(System.in)){
            n = sc.nextInt();
            scores = new int[n][4];
            for (int i = 0; i < n; i++) {
                scores[i][0] = sc.nextInt();
                scores[i][1] = sc.nextInt();
                scores[i][2] = sc.nextInt();
                scores[i][3] = i + 1;
            }
        }

        Arrays.sort(scores, ((o1, o2) -> {
            int t1 = o1[0] + o1[1] + o1[2], t2 = o2[0] + o2[1] + o2[2];
            if(t1 == t2){
                if(o1[0] == o2[0]){
                    return o1[3] - o2[3];
                }else{
                    return o2[0] - o1[0];
                }
            }
            return t2 - t1;
        }));

        for (int i = 0; i < 5; i++) {
            int t = scores[i][0] + scores[i][1] + scores[i][2];
            System.out.println(scores[i][3] + " " + t);
        }
    }
}



活动打卡代码 AcWing 422. 校门外的树

Sei
9个月前
import java.io.IOException;
import java.util.Scanner;
import java.util.Arrays;
public class Main {

    /**
     * 数据范围
     * 1≤L≤10000,
     * 1≤M≤100
     * 输入样例:
     * 500 3
     * 150 300
     * 100 200
     * 470 471
     * @param args
     */
    public static void main(String[] args) throws IOException {
        final int L, n;
        int[][] tree;
        try(Scanner sc = new Scanner(System.in)){
            L = sc.nextInt(); n = sc.nextInt();
            tree = new int[n][2];
            for (int i = 0; i < n; i++) {
                tree[i][0] = sc.nextInt();
                tree[i][1] = sc.nextInt();
            }
        }
        Arrays.sort(tree, (o1, o2) -> o1[0] - o2[0]);
        int l = tree[0][0], r = tree[0][1];
        int res = L + 1;
        for (int i = 1; i < n; i++) {
            if(tree[i][0] <= r){
                r = Math.max(tree[i][1], r);
            }else{
                res -= r - l + 1;
                l = tree[i][0]; r = tree[i][1];
            }
        }
        res -= r - l +1;
        System.out.println(res);
    }
}




Sei
9个月前

题目描述

blablabla

样例

blablabla

算法

(向上dp) $O(n^2)$

java 代码


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {

    /**
     * 5
     * 7
     * 3 8
     * 8 1 0
     * 2 7 4 4
     * 4 5 2 6 5
     * 1≤n≤500,
     * −10000≤三角形中的整数≤10000
     * @param args
     */
    public static void main(String[] args) throws IOException {
        int[][] triangle;
        final int n;
        try(BufferedReader bd = new BufferedReader(new InputStreamReader(System.in))){
            n = Integer.parseInt(bd.readLine());
            triangle = new int[n][n];
            for (int i = 0; i < n; i++) {
                String[] s = bd.readLine().split(" ");
                for (int j = 0; j < s.length; j++) {
                    triangle[i][j] = Integer.parseInt(s[j]);
                }
            }
        }

        for (int i = n-2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                triangle[i][j] = triangle[i][j] + Math.max(triangle[i+1][j], triangle[i+1][j+1]);
            }
        }
        System.out.println(triangle[0][0]);

    }

}
blablabla