头像

赵暑涛

广西民族师范学院




离线:5小时前



y总的分析


895 动态规划 DP 最长上升子序列.jpg

import java.io.*;

public class Main {
    static int n;
    static final int N = 1010;
    static int[] a = new int[N]; // 存放数据
    static int[] f = new int[N]; // 存放结果
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(in.readLine());
        String[] data = in.readLine().split(" ");
        for (int i = 1; i <= n; i++)
            a[i] = Integer.parseInt(data[i - 1]);

        int res = 0;
        for (int i = 1; i <= n; i++) {
            f[i] = 1; // 只有自己本身就是1
            for (int j = 1; j < i; j++)
                // 小于a[i] 才是以a[i]结尾的上升子序列
                // 每一个小于自己的上升子序列加上1(自己)和自己原最长上升子序列比较
                if (a[j] < a[i]) f[i] = Math.max(f[i], f[j] + 1);
            res = Math.max(res, f[i]); // 每次更新最长子序列的最大值
        }

        System.out.println(res);
        in.close();
    }
}


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

y总的分析


1015 动态规划 DP 摘花生.jpg

import java.io.*;

public class Main {
    static int t, r, c;
    static final int N = 1010;
    static int[][] f = new int[N][N];
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        t = Integer.parseInt(in.readLine());
        while (t-- > 0) {
            String[] init = in.readLine().split(" ");
            r = Integer.parseInt(init[0]);
            c = Integer.parseInt(init[1]);
            for (int i = 1; i <= r; i++) {
                String[] data = in.readLine().split(" ");
                for (int j = 1; j <= c; j++)
                    f[i][j] = Integer.parseInt(data[j - 1]);
            }
            for (int i = 1; i <= r; i++)
                for (int j = 1; j <= c; j++)
                    // 每次都加上从上往下来和从左往右过来的最大值
                    f[i][j] += Math.max(f[i - 1][j], f[i][j - 1]);
            System.out.println(f[r][c]);
        }
        in.close();
    }
}


活动打卡代码 AcWing 2. 01背包问题

y总的分析


2 DP 01背包问题.jpg
2_2 DP 背包问题.jpg

import java.io.*;

public class Main {
    static int n, m;
    static final int N = 1010;
    static int[] v = new int[N]; // 价值
    static int[] w = new int[N]; // 体积
    static int[] f1 = new int[N]; // 一维

    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        String[] init = in.readLine().split(" ");
        n = Integer.parseInt(init[0]);
        m = Integer.parseInt(init[1]);

        for (int i = 1; i <= n; i++) { // 从 1 开始 一个物品都不选的情况都是0
            String[] data = in.readLine().split(" ");
            v[i] = Integer.parseInt(data[0]);
            w[i] = Integer.parseInt(data[1]);
        }

        // 一维
        for (int i = 1; i <= n; i++)
            for (int j = m; j >= v[i]; j--) // 从大到小枚举
                // 才能使得 f[j - v[i]] 变成上一种选择方案的最大价值 + 当前选择物品的价值
                f1[j] = Math.max(f1[j], f1[j - v[i]] + w[i]);

        System.out.println(f1[m]); // 一维
        in.close();
    }
}
import java.io.*;

public class Main {
    static int n, m;
    static final int N = 1010;
    static int[] v = new int[N]; // 价值
    static int[] w = new int[N]; // 体积
    static int[][] f2 = new int[N][N]; // 二维
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        String[] init = in.readLine().split(" ");
        n = Integer.parseInt(init[0]);
        m = Integer.parseInt(init[1]);

        for (int i = 1; i <= n; i++) { // 从 1 开始 一个物品都不选的情况都是0
            String[] data = in.readLine().split(" ");
            v[i] = Integer.parseInt(data[0]);
            w[i] = Integer.parseInt(data[1]);
        }

        //二维
        for (int i = 1; i <= n; i++) { // 从选第 1 个物品开始考虑
            for (int j = 0; j <= m; j++) { // j = 0 就是体积为 0 总价值也为 0
                f2[i][j] = f2[i - 1][j]; // 每次让新的选择方法先初始化为 上一次的最大值方案
                // 如果选择了新物品的最大价值还没有上一次的价值大 就不选择 也就相当于不选第 i 个物品

                // j 是体积, 当前选择方案的体积要大于当前选择物品体积, 才能去选择
                if (j >= v[i]) f2[i][j] = Math.max(f2[i][j], f2[i - 1][j - v[i]] + w[i]);
                // max() 里比较的是 不选择第 i 个物品 和选择第 i 个物品的最大价值
                // j - v[i] 就是 先减去当前第 i 个物品的体积 然后看一下对应的 f[i - 1][j - v[i]]的体积是多少
                // 比如 f[1][1] = 2
                // 选择到第 2 个物品, 体积为 2 时, 第 2 个物品 体积是 1(v[i]) 价值是 2(w[i])
                // f[2][2] = f[2 - 1][2 - 1] + 2 = 4 ,也就是 再减去了当前第 i 个物品的体积后再加上原有的体积对应的价值
            }
        }
        System.out.println(f2[n][m]); // 二维

        in.close();
    }
}


活动打卡代码 AcWing 1216. 饮料换购

y总的分析


1216 数学 饮料换购.jpg

import java.io.*;

public class Main {
    static int n;
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(in.readLine());
        int res = n;

        while (n > 2) {
            res += n / 3;
            n = n / 3 + n % 3;
        }

        System.out.println(res);
        in.close();
    }
}


活动打卡代码 AcWing 1211. 蚂蚁感冒

y总的分析


1211 数学 蚂蚁感冒.jpg

import java.io.*;

public class Main {
    static int n;
    static final int N = 60;
    static int[] a = new int[N];
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(in.readLine());
        String[] data = in.readLine().split(" ");

        for (int i = 0; i < n; i++)
            a[i] = Integer.parseInt(data[i]);

        // 分别表示左边向右走的蚂蚁数量, 右边向左走的蚂蚁数量
        int left = 0, right = 0;
        for (int i = 1; i < n; i++)
            // 在被感染蚂蚁左边但是向右走的蚂蚁 也就是正数
            if (Math.abs(a[i]) < Math.abs(a[0]) && a[i] > 0) left++;
                // 在被感染蚂蚁右边但是向左走的蚂蚁 也就是负数
            else if (Math.abs(a[i]) > Math.abs(a[0]) && a[i] < 0) right++;

        // 感染蚂蚁向右走并且右边没有向左走的蚂蚁 或者 感染蚂蚁向左走并且左边没有向右走的蚂蚁
        if (a[0] > 0 && right == 0 || a[0] < 0 && left == 0)
            System.out.println(1);
            // 否则就是感染蚂蚁向左或者右方向走的时候左右两边都有走向感染蚂蚁的蚂蚁
            // 就用 left + right + 1 (最开始的感染蚂蚁)
        else
            System.out.println(left + right + 1);
    }
}


活动打卡代码 AcWing 1205. 买不到的数目

y总的分析


1205 数学 打表找规律 买不到的数目.jpg

import java.io.*;

public class Main {
    static int n, m;
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        String[] init = in.readLine().split(" ");
        n = Integer.parseInt(init[0]);
        m = Integer.parseInt(init[1]);
        System.out.println((n - 1) * (m - 1) - 1);
        in.close();
    }
}


活动打卡代码 AcWing 1230. K倍区间

y总的分析


1230 前缀和 K倍区间.jpg

import java.io.*;

public class Main {
    static int n, k;
    static final int N = 100010;
    static int[] s = new int[N];
    static int[] c = new int[N];
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        String[] init = in.readLine().split(" ");
        n = Integer.parseInt(init[0]);
        k = Integer.parseInt(init[1]);

        for (int i = 1; i <= n; i++)
            s[i] = (s[i - 1] + Integer.parseInt(in.readLine())) % k;

        long res = 0;
        c[0] = 1;
        for (int i = 1; i <= n; i++) {
            res += c[s[i]];
            c[s[i]]++;
        }
        System.out.println(res);
        in.close();
    }
}


活动打卡代码 AcWing 99. 激光炸弹

y总的分析


99_1 二维前缀和 激光炸弹.jpg
99_2 二维前缀和 激光炸弹.jpg

import java.io.*;

public class Main {
    static int n, R;
    static final int N = 5010;
    static int[][] s = new int[N][N];
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        String[] init = in.readLine().split(" ");
        n = Integer.parseInt(init[0]);
        R = Integer.parseInt(init[1]);

        int r, c;
        R = Math.min(5001, R); // R 最大 5001 再大意义也不大
        r = c = R; // r 和 c 表示 行 和 列 设置为和 R 一样大 来保证右下角一定存在

        while (n-- > 0) {
            String[] data = in.readLine().split(" ");
            int x = Integer.parseInt(data[0]) + 1; // + 1 保证 >= 1 防止边界问题
            int y = Integer.parseInt(data[1]) + 1; // + 1 保证 >= 1 防止边界问题
            int w = Integer.parseInt(data[2]);
            r = Math.max(r, x); // r 横坐标更新为最大值
            c = Math.max(c, y); // c 纵坐标更新为最大值
            s[x][y] += w;
        }

        // 预处理前缀和
        for (int i = 1; i <= r; i++)
            for (int j = 1; j <= c; j++)
                s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];

        int res = 0;

        // 枚举所有边长是 R 的矩形, 枚举 (i, j) 为右下角
        for (int i = R; i <= r; i++)
            for (int j = R; j <= c; j++)
                res = Math.max(res, s[i][j] - s[i - R][j] - s[i][j - R] + s[i - R][j - R]);

        System.out.println(res);
        in.close();
    }
}


活动打卡代码 AcWing 796. 子矩阵的和

赵暑涛
10天前

y总的分析


796_1 子矩阵的和.jpg
796_2 子矩阵的和.jpg
796_3 子矩阵的和.jpg

import java.io.*;

public class Main {
    static int n, m, q;
    static final int N = 1010;
    static int[][] s = new int[N][N];
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] init = in.readLine().split(" ");
        n = Integer.parseInt(init[0]);
        m = Integer.parseInt(init[1]);
        q = Integer.parseInt(init[2]);

        for (int i = 1; i <= n; i++) {
            String[] data = in.readLine().split(" ");
            for (int j = 1; j <= m; j++) {
                s[i][j] = Integer.parseInt(data[j - 1]);
                s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]; // 核心
            }
        }

        while (q-- > 0) {
            String[] info = in.readLine().split(" ");
            int x1 = Integer.parseInt(info[0]);
            int y1 = Integer.parseInt(info[1]);
            int x2 = Integer.parseInt(info[2]);
            int y2 = Integer.parseInt(info[3]);
            out.write(s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] + "\n"); // 核心
        }

        in.close();
        out.flush();
        out.close();
    }
}


活动打卡代码 AcWing 795. 前缀和

赵暑涛
10天前

y总的分析


795 前缀和.jpg

import java.io.*;

public class Main {
    static int n, m;
    static final int N = 100010;
    static int[] s = new int[N];
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] init = in.readLine().split(" ");
        n = Integer.parseInt(init[0]);
        m = Integer.parseInt(init[1]);

        String[] data = in.readLine().split(" ");
        for (int i = 1; i <= n; i++) // 下标从 1 开始
            s[i] = s[i - 1] + Integer.parseInt(data[i - 1]);
        // 原数组: a[1], a[2], a[3], a[4], a[5], …, a[n]
        // 前缀和 Si为数组的前 i项和
        // 前缀和: S[i] = a[1] + a[2] + a[3] + … + a[i]

        while (m-- > 0) {
            String[] info = in.readLine().split(" ");
            int l = Integer.parseInt(info[0]);
            int r = Integer.parseInt(info[1]);
            out.write(s[r] - s[l - 1] + "\n");
            // q[r] - q[l - 1] 从 1 开始防止 l - 1 越界
            // 对于 l ~ r ; r 是已经包含了 l + (l + 1) + … + r 的,
            // 用 r - (l - 1) 就是用 r 中 l 之前的元素
            // 0 2 1 3 6  4
            // 0 2 3 6 12 16
            // 3 ~ 5 = 5 - (3 - 1) = 5 - 2 = 16 - 3 = 13
            // 5 = 5 + 4 + 3 + 2 + 1
            // 3 = 3 + 2 + 1
            // 这里要保留 3 就要去掉 2 + 1, 刚好 l - 1 = 2 = 2 + 1 就满足
            // 所以 5 - 2 = 5 + 4 + 3 + 2 + 1 - 2 - 1 = 5 + 4 + 3 = 13
        }
        in.close();
        out.flush();
        out.close();
    }
}