蓝桥算法训练__普及组.Day11

第一题：P1757 通天之分组背包 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

package 蓝桥算法训练__普及组.Day11;

import java.io.*;

/**
 * @author snippet
 * @data 2023-02-15
 * P1757 通天之分组背包 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
 */
// 分组背包
public class T1 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer st = new StreamTokenizer(br);
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));

    static int n,m,x,t;// n表示总重量 m表示总物品数 x表示小组数 t表示最大小组数
    static int[] w = new int[1100];// 表示第i个物品的重量
    static int[] val = new int[1100];// 表示第i个物品的利用价值
    static int[] b = new int[1100];// 表示第i组的第几个物品
    static int[] dp = new int[1100];// 表示重量为i时的最大利用价值
    static int[][] g = new int[1100][1100];// 表示第i组的第j个物品的编号

    public static void main(String[] args) throws IOException {
        n = nextInt();
        m = nextInt();
        for (int i = 1; i <= m; i++) {
            w[i] = nextInt();
            val[i] = nextInt();
            x = nextInt();
            // 记录最大小组数
            t = Math.max(t,x);
            // 记录每个组有多少个物品
            b[x]++;
            // 记录第i组的第j个物品的编号
            g[x][b[x]] = i;
        }

        // i表示小组数
        for (int i = 1; i <= t; i++) {
            // j表示重量(n->0)
            for (int j = n; j >= 0; j--) {
                // k表示第i个小组共有多少物品
                for (int k = 1; k <= b[i]; k++) {
                    // 当j的重量 >= 第i组第k个物品的重量时
                    // 进行dp 状态转移
                    if (j >= w[g[i][k]]) {
                        dp[j] = Math.max(dp[j], dp[j-w[g[i][k]]]+val[g[i][k]]);
                    }
                }
            }
        }

        pw.println(dp[n]);
        pw.flush();
    }

    static int nextInt() throws IOException {
        st.nextToken();
        return (int) st.nval;
    }
}

第二题：P1832 A+B Problem（再升级） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

package 蓝桥算法训练__普及组.Day11;

import java.io.*;

/**
 * @author snippet
 * @data 2023-02-15
 * P1832 A+B Problem（再升级） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
 */
// 完全背包
public class T2 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer st = new StreamTokenizer(br);
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));

    static int n;
    static long[] dp = new long[1100];
    static boolean[] is = new boolean[1100];// 存第i个数是不是素数 false表示是 反之true表示不是

    // 用筛法求素数
    static void prime() {
        for (int i = 2; i <= 500; i++) {
            // false表示这个数是素数
            if (!is[i]) {
                for (int j = 2; i*j <= 1000; j++) {
                    is[i*j] = true;
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        prime();
        n = nextInt();
        // 完全背包的经典预处理
        dp[0] = 1;
        for (int i = 2; i <= n; i++) {
            // 是素数的情况下才进行考虑
            // false表示i是素数
            if (!is[i]) {
                // 第j个数由素数的组成情况 dp[j]+=dp[j-i]也就是加上j-i这个数的可以由素数的组成方案
                for (int j = i; j <= n; j++) {
                    dp[j] += dp[j-i];
                }
            }
        }
        pw.println(dp[n]);
        pw.flush();
    }

    static int nextInt() throws IOException {
        st.nextToken();
        return (int) st.nval;
    }
}

第三题：P1203 [USACO1.1] 坏掉的项链 Broken Necklace - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

package 蓝桥算法训练__普及组.Day11;

import java.io.*;

/**
 * @author snippet
 * @data 2023-02-15
 * P1203 [USACO1.1] 坏掉的项链 Broken Necklace - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
 */
// 双指针
public class T3 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer st = new StreamTokenizer(br);
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));

    static int n,sum;// n表示这串珠子的个数 sum表示收集珠子最大数(小于n)
    static char[] c = new char[710];// 字符数组c表示这串珠子每个的颜色

    public static void main(String[] args) throws IOException {
        String[] s = br.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        s = br.readLine().split(" ");
        String str = s[0];
        for (int i = 0; i < n; i++) {
            c[i] = str.charAt(i);
        }
        // 首尾相串
        for (int i = n; i < 2*n; i++) {
            c[i] = c[i-n];
        }

        for (int i = 0; i < 2*n; i++) {
            int left = i, right = i+1;
            char c1 = c[left], c2 = c[right];

            // 特判 当该位置为白色w时 往前搜索一个位置 如果不特判的话会少计算一些珠子
            if (c1 == 'w' && left > 1) {
                c1 = c[left-1];
            } else if(c2 == 'w' && right > 1) {
                c2 = c[right-1];
            }

            int num = 0;// 收集的珠子的个数
            while (left >= 0) {
                if (c[left] == c1 || c[left] == 'w') {
                    num++;
                } else {
                    break;
                }
                left--;
            }
            while (right < 2*n) {
                if (c[right] == c2 || c[right] == 'w') {
                    num++;
                } else {
                    break;
                }
                right++;
            }
            sum = Math.max(sum, num);
        }
        // 得到的珠子肯定是小于n
        pw.println(Math.min(sum,n));
        pw.flush();
    }

    static int nextInt() throws IOException {
        st.nextToken();
        return (int)st.nval;
    }
}