头像

幼儿园小班长


访客:794

离线:5天前



import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            a[i] = in.nextInt();
        }

        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = 1;
            for (int j = 1; j < i; j++) {
                if (a[i] > a[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        int res = 0;
        for (int i = 1; i <= n; i++) {
            res = Math.max(res, dp[i]);
        }
        System.out.println(res);
    }
}


活动打卡代码 AcWing 1018. 最低通行费

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][] a = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                a[i][j] = in.nextInt();
            }
        }

        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == 1) {
                    dp[j] = dp[j - 1] + a[i][j];
                } else if (j == 1) {
                    dp[j] += a[i][j];
                } else {
                    dp[j] = Math.min(dp[j], dp[j - 1]) + a[i][j];
                }
            }
        }

        System.out.println(dp[n]);
    }
}


活动打卡代码 AcWing 1015. 摘花生

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int k = in.nextInt();
        while (k -- > 0) {
            int m = in.nextInt(), n = in.nextInt();
            int[][] a = new int[m + 1][n + 1];
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    a[i][j] = in.nextInt();
                }
            }

            int[] dp = new int[n + 1];
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    dp[j] = Math.max(dp[j], dp[j - 1]) + a[i][j];
                }
            }

            System.out.println(dp[n]);
        }
    }
}



import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt(), n = in.nextInt();
        char[] s1 = new char[m + 1];
        char[] s2 = new char[n + 1];
        String str1 = in.next(), str2 = in.next();
        for (int i = 1; i <= m; i++) {
            s1[i] = str1.charAt(i - 1);
        }
        for (int i = 1; i <= n; i++) {
            s2[i] = str2.charAt(i - 1);
        }

        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1[i] == s2[j]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
                dp[i][j] = Math.max(dp[i][j], dp[i][j - 1]);
            }
        }

        System.out.println(dp[m][n]);
    }
}


活动打卡代码 AcWing 898. 数字三角形

这个题主要要注意下初始化

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][] arr = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                arr[i][j] = in.nextInt();
            }
        }

        int[][] dp = new int[n + 1][n + 10];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= i + 1; j++) {
                dp[i][j] = Integer.MIN_VALUE;
            }
        }

        dp[1][1] = arr[1][1];
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + arr[i][j];
            }
        }

        int max = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            max = Math.max(max, dp[n][i]);
        }

        System.out.println(max);
    }
}


活动打卡代码 AcWing 4. 多重背包问题

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), V = in.nextInt();
        int[] v = new int[n + 1];
        int[] w = new int[n + 1];
        int[] s = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            v[i] = in.nextInt();
            w[i] = in.nextInt();
            s[i] = in.nextInt();
        }

        int[][] dp = new int[n + 1][V + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= V; j++) {
                for (int k = 0; k <= s[i] && k * v[i] <= j; k++) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]);
                }
            }
        }

        System.out.println(dp[n][V]);
    }
}


活动打卡代码 AcWing 423. 采药

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int V = in.nextInt(), n = in.nextInt();
        int[] v = new int[n + 1];
        int[] w = new int[n + 1];
        for (int i = 1; i <= n ; i++) {
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }

        int[] dp = new int[V + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = V; j >= v[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
            }
        }

        System.out.println(dp[V]);
    }
}


活动打卡代码 AcWing 1116. 马走日

import java.util.*;

public class Main {
    private static int res;
    private static int[] dx = {-2, -1, 1, 2, 2, 1, -1, -2};
    private static int[] dy = {1, 2, 2, 1, -1, -2, -2, -1};

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int k = in.nextInt();
        while (k-- > 0) {
            int m = in.nextInt(), n = in.nextInt(), x = in.nextInt(), y = in.nextInt();
            boolean[][] visited = new boolean[m][n];
            res = 0;
            dfs(visited, x, y, 1);
            System.out.println(res);
        }
    }

    private static void dfs(boolean[][] visited, int x, int y, int cnt) {
        int m = visited.length, n = visited[0].length;
        if (cnt == m * n) {
            res++;
            return;
        }
        visited[x][y] = true;
        for (int i = 0; i < 8; i++) {
            int tx = x + dx[i], ty = y + dy[i];
            if (tx < 0 || tx >= m || ty < 0 || ty >= n || visited[tx][ty]) {
                continue;
            }
            dfs(visited, tx, ty, cnt + 1);
        }
        visited[x][y] = false;
    }
}


活动打卡代码 AcWing 1113. 红与黑

import java.util.*;

public class Main {
    private static int[] dx = {-1, 1, 0, 0};
    private static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (true) {
            int n = in.nextInt(), m = in.nextInt();
            if (n == 0 && m == 0) {
                break;
            }
            char[][] grid = new char[m][n];
            int x = 0, y = 0;
            for (int i = 0; i < m; i++) {
                char[] chs = in.next().toCharArray();
                for (int j = 0; j < n; j++) {
                    grid[i][j] = chs[j];
                    if (grid[i][j] == '@') {
                        x = i;
                        y = j;
                    }
                }
            }

            System.out.println(dfs(grid, x, y));
        }
    }

    private static int dfs(char[][] grid, int x, int y) {
        int res = 1;
        grid[x][y] = '#';
        for (int i = 0; i < 4; i++) {
            int tx = x + dx[i], ty = y + dy[i];
            if (tx < 0 || tx >= grid.length || ty < 0 || ty >= grid[0].length || grid[tx][ty] != '.') {
                continue;
            }
            res += dfs(grid, tx, ty);
        }
        return res;
    }
}


活动打卡代码 AcWing 1112. 迷宫

import java.util.*;

public class Main {
    private static int[] dx = {-1, 1, 0, 0};
    private static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int k = in.nextInt();
        while (k-- > 0) {
            int n = in.nextInt();
            char[][] grid = new char[n][n];
            for (int i = 0; i < n; i++) {
                char[] chs = in.next().toCharArray();
                for (int j = 0; j < n; j++) {
                    grid[i][j] = chs[j];
                }
            }
            int x1 = in.nextInt(), y1 = in.nextInt(), x2 = in.nextInt(), y2 = in.nextInt();

            if (grid[x1][y1] == '#' || grid[x2][y2] == '#') {
                System.out.println("NO");
                continue;
            }
            boolean res = dfs(grid, x1, y1, x2, y2,n);
            System.out.println(res ? "YES" : "NO");
        }
    }

    private static boolean dfs(char[][] grid, int x1, int y1, int x2, int y2, int n) {
        if (x1 == x2 && y1 == y2) {
            return true;
        }
        grid[x1][y1] = '#';
        boolean res = false;
        for (int i = 0; i < 4; i++) {
            int tx = x1 + dx[i], ty = y1 + dy[i];
            if (tx < 0 || tx >= n || ty < 0 || ty >= n || grid[tx][ty] == '#') {
                continue;
            }
            res = res || dfs(grid, tx, ty, x2, y2, n);
        }
        return res;
    }
}