头像

夏日的小提琴




离线:10小时前


最近来访(25)
用户头像
RyanMoriarty
用户头像
C艹
用户头像
Pipipapi
用户头像
Gamkiu
用户头像
ysl0310
用户头像
lxm
用户头像
寻欢
用户头像
123go
用户头像
空银子
用户头像
葡萄味的QQ糖
用户头像
Q_83
用户头像
трава
用户头像
用户头像
平卉陌路
用户头像
神明的救续
用户头像
warnder
用户头像
李云龙
用户头像
星逐月丶
用户头像
wangdong
用户头像
醉生梦死

活动打卡代码 AcWing 900. 整数划分

import java.io.*;

public class Main {
    static int n;
    static final int mod = (int) Math.pow(10, 9) + 7;
    static int[][] f;
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(reader.readLine());
        f = new int[n + 1][n + 1];
        for (int i = 0; i <= n; i++) f[i][0] = 1;//表示当容量为0,我每次一件物品都不选,就是一种方案

        for (int i = 1; i <= n; i++) {//遍历每件物品,1-n,每件物品体积就是i
            for (int j = 1; j <= n; j++) {//遍历背包容量,1-n
                if (i > j) {
                    f[i][j] = f[i - 1][j] % mod;//表示当物品体积超过容量j时,只能不选
                } else {
                    f[i][j] = (f[i - 1][j] + f[i][j - i]) % mod;//求出所有情况的和(优化后的写法)
                }
            }
        }
        writer.write(f[n][n] + "");
        writer.flush();
        writer.close();
        reader.close();

    }
}



import java.io.*;

public class Main {
    static int n;
    static final int mod = (int) Math.pow(10, 9) + 7;
    static int[][] f;
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(reader.readLine());
        f = new int[n + 1][n + 1];
        for (int i = 0; i <= n; i++) f[i][0] = 1;//表示当容量为0,我每次一件物品都不选,就是一种方案

        for (int i = 1; i <= n; i++) {//遍历每件物品,1-n,每件物品体积就是i
            for (int j = 1; j <= n; j++) {//遍历背包容量,1-n
                if (i > j) {
                    f[i][j] = f[i - 1][j] % mod;//表示当物品体积超过容量j时,只能不选
                } else {
                    f[i][j] = (f[i - 1][j] + f[i][j - i]) % mod;//求出所有情况的和(优化后的写法)
                }
            }
        }
        writer.write(f[n][n] + "");
        writer.flush();
        writer.close();
        reader.close();

    }
}


活动打卡代码 AcWing 282. 石子合并

import java.io.*;

public class Main {
    static int n;
    static int[] s;//s是前缀和
    static int[][] f;
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(reader.readLine());
        s = new int[n + 1];
        f = new int[n + 1][n + 1];
        String[] str = reader.readLine().split(" ");
        for (int i = 1; i <= n; i++) {
            s[i] = Integer.parseInt(str[i - 1]);
            s[i] += s[i - 1];
        }

        //区间dp问题的两层外循环一般是:第一层是区间长度N,第二层是从区间左端点开始,同时保证区间右端点在区间范围内
        for (int len = 2; len <= n; len++) {//长度为1,表示已经是1堆,消耗体力为0,不用枚举
            for (int i = 1; i <= n - len + 1; i++) {
                int j = i + len - 1;//从i开始,长度为len时,j的下标
                f[i][j] = Integer.MAX_VALUE;
                for (int k = i; k < j; k++) {//接着枚举能将i-j分为两堆的分割点,并取消耗体力最小的选法
                    f[i][j] = Math.min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
                }
            }

        }

        //则最终f[1][n]为我们要求的答案,因为表示是将1到n合为一堆的体力消耗最小值,即就是题目问我们的问题
        writer.write(f[1][n] + "");
        writer.flush();
        writer.close();
        reader.close();
    }
}



import java.io.*;

public class Main {
    static int n;
    static int[] s;//s是前缀和
    static int[][] f;
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(reader.readLine());
        s = new int[n + 1];
        f = new int[n + 1][n + 1];
        String[] str = reader.readLine().split(" ");
        for (int i = 1; i <= n; i++) {
            s[i] = Integer.parseInt(str[i - 1]);
            s[i] += s[i - 1];
        }

        //区间dp问题的两层外循环一般是:第一层是区间长度N,第二层是从区间左端点开始,同时保证区间右端点在区间范围内
        for (int len = 2; len <= n; len++) {//长度为1,表示已经是1堆,消耗体力为0,不用枚举
            for (int i = 1; i <= n - len + 1; i++) {
                int j = i + len - 1;//从i开始,长度为len时,j的下标
                f[i][j] = Integer.MAX_VALUE;
                for (int k = i; k < j; k++) {//接着枚举能将i-j分为两堆的分割点,并取消耗体力最小的选法
                    f[i][j] = Math.min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
                }
            }

        }

        //则最终f[1][n]为我们要求的答案,因为表示是将1到n合为一堆的体力消耗最小值,即就是题目问我们的问题
        writer.write(f[1][n] + "");
        writer.flush();
        writer.close();
        reader.close();
    }
}


活动打卡代码 AcWing 902. 最短编辑距离

import java.io.*;

public class Main {
    static int n, m;
    static int[][] f;
    static char[] a;
    static char[] b;
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(reader.readLine());
        a = reader.readLine().toCharArray();
        m = Integer.parseInt(reader.readLine());
        b = reader.readLine().toCharArray();
        f = new int[n + 1][m + 1];

        //初始化f[0][k] 和 f[k][0]
        for (int i = 0; i <= n; i++) f[i][0] = i;//表示将有i个字符的A变为空的B,最少是通过删除i步得到
        for (int i = 0; i <= m; i++) f[0][i] = i;//表示将空的A变为有i个字符的B,最少是通过增加i步得到

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

        writer.write(f[n][m] + "");
        writer.flush();
        writer.close();
        reader.close();
    }
}



import java.io.*;

public class Main {
    static int n, m;
    static int[][] f;
    static char[] a;
    static char[] b;
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(reader.readLine());
        a = reader.readLine().toCharArray();
        m = Integer.parseInt(reader.readLine());
        b = reader.readLine().toCharArray();
        f = new int[n + 1][m + 1];

        //初始化f[0][k] 和 f[k][0]
        for (int i = 0; i <= n; i++) f[i][0] = i;//表示将有i个字符的A变为空的B,最少是通过删除i步得到
        for (int i = 0; i <= m; i++) f[0][i] = i;//表示将空的A变为有i个字符的B,最少是通过增加i步得到

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

        writer.write(f[n][m] + "");
        writer.flush();
        writer.close();
        reader.close();
    }
}



import java.io.*;

public class Main {
    static int n, m;
    static int[][] f;
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] str = reader.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        m = Integer.parseInt(str[1]);
        f = new int[n + 1][m + 1];
        char[] a = reader.readLine().toCharArray();
        char[] b = reader.readLine().toCharArray();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (a[i - 1] == b[j - 1]) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                } else {
                    f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
                }
            }
        }
        writer.write(f[n][m] + "");
        writer.flush();
        writer.close();
        reader.close();
    }
}



import java.io.*;

public class Main {
    static int n, m;
    static int[][] f;
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] str = reader.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        m = Integer.parseInt(str[1]);
        f = new int[n + 1][m + 1];
        char[] a = reader.readLine().toCharArray();
        char[] b = reader.readLine().toCharArray();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (a[i - 1] == b[j - 1]) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                } else {
                    f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
                }
            }
        }
        writer.write(f[n][m] + "");
        writer.flush();
        writer.close();
        reader.close();
    }
}



import java.io.*;

public class Main {
    static int[] a;
    static int[] f;
    static int n;
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(reader.readLine());
        a = new int[n];
        f = new int[n+1];
        int len = 0;
        String[] str = reader.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(str[i]);
        }
        for (int i = 0; i < n; i++) {
            int l = 0;
            int r = len;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (f[mid] < a[i]) l = mid; //如果中间值小于a[i],则继续往右找,直到找到第一个大于等于a[i]的停止(找左边小于a[i]的第一个最大值)
                else r = mid - 1;
            }
            len = Math.max(len, r + 1);//更新单调递增序列的最大长度
            f[r + 1] = a[i];//将a[i]接到找到第一个小于它的最大值,即左大
        }

        writer.write(len + "");
        writer.flush();
        writer.close();
        reader.close();
    }
}



import java.io.*;

public class Main {
    static int[] a;
    static int[] f;
    static int n;
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(reader.readLine());
        a = new int[n];
        f = new int[n+1];
        int len = 0;
        String[] str = reader.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(str[i]);
        }
        for (int i = 0; i < n; i++) {
            int l = 0;
            int r = len;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (f[mid] < a[i]) l = mid; //如果中间值小于a[i],则继续往右找,直到找到第一个大于等于a[i]的停止(找左边小于a[i]的第一个最大值)
                else r = mid - 1;
            }
            len = Math.max(len, r + 1);//更新单调递增序列的最大长度
            f[r + 1] = a[i];//将a[i]接到找到第一个小于它的最大值,即左大
        }

        writer.write(len + "");
        writer.flush();
        writer.close();
        reader.close();
    }
}