个人空间 - AcWing

鼠鼠我

山东科技大学

关注数

粉丝数

阅读量

6747

+关注发消息

离线：1天前

题目描述

blablabla

JAVA 代码


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N = 310;
    static int[] a = new int[N];
    static int[][] f = new int[N][N];//f[i][j]表示将所有[i-j]合并成一堆的方案集合，取最小值
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String s[] = br.readLine().split(" ");
        for (int i = 1; i <= n; i++) {
            a[i] = Integer.parseInt(s[i-1]);
            a[i] += a[i-1];//区间和
        }
        //套路:先枚举区间长度
        for (int len = 2; len <= n; len++) {//从2开始
            for (int i = 1; i + len -1 <= n; i++) {//枚举左区间，减一是左区间最多到n-1，然后右区间留一个
                int j = i + len -1;
                f[i][j] = (int) 1e8;
                for (int k = i; k < j; k++) {//k最多到j-1，
                    f[i][j] = Math.min(f[i][j],f[i][k] + f[k+1][j] + a[j] - a[i-1]);
                }
            }
        }
        System.out.println(f[1][n]);
    }
}

题解 AcWing 899. 编辑距离（JAVA）

鼠鼠我
1天前

题目描述

blablabla

JAVA 代码


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N = 1010;
    static String[] p = new String[N];//n个字符串
    static String q[] = new String[N];//m个字符串
    static int[][] f = new int[N+10][N+10];////所有将a[1-i]变成b[1-j]的操作方式
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s1[] = br.readLine().split(" ");
        int n = Integer.parseInt(s1[0]);
        int m = Integer.parseInt(s1[1]);
        for (int i = 1; i <= n; i++) {
            p[i] = br.readLine();
        }

        for (int i = 1; i <= m; i++) {
            int res = 0;
            q[i] = br.readLine();
            char[] a = q[i].split(" ")[0].toCharArray();
            int limit = Integer.parseInt(q[i].split(" ")[1]);
            for (int j = 1; j <= n; j++) {//判断有多少个字符串和当前的字符串能够在限制的次数下匹配
                char[] b = p[j].toCharArray();
                if(limit_distance(a,b) <= limit){
                    res++;
                }
            }
            System.out.println(res);
        }

    }
    static int limit_distance(char[] a,char[] b){//a是询问的字符串，b是给定的字符串
        for (int i = 0; i <= b.length; i++) f[0][i] = i;
        for (int i = 0; i <= a.length; i++) f[i][0] = i;

        for (int i = 1; i <= a.length; i++) {
            for (int j = 1; j <= b.length; 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);
            }
        }
        return f[a.length][b.length];
    }
}

题解 AcWing 902. 最短编辑距离（JAVA）

鼠鼠我
2天前

题目描述

blablabla

JAVA代码


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    /**
     * 状态计算分为三种情况
     * 删除：在删掉i之前a[i-1]和b[j]是相同的，用f[i-1][j]表示a[i-1]变成b[j]的操作方式的最小值，f[i-1][j]+1表示加一步删除的操作
     * 增加：在添加j之前a[i]和b[j-1]是相同的，用f[i][j-1]表示a[i]变成b[j-1]的操作方式的最小值，f[i][j-1]+1表示加一步添加的操作
     * 改：在添加i之前a[i-1]和b[j-1]是相同的，用f[i-1][j-1]表示a[i-1]变成b[j-1]的操作方式的最小值，如果相同a[i]和b[j]相同，f[i][j]不用，如果不同，f[i][j]=f[i-1][j-1]+1;
     * */
    static int N = 1010;
    static char[] a = new char[N];
    static char[] b = new char[N];
    static int [][] f = new int[N][N];//所有将a[1-i]变成b[1-j]的操作方式的最小值
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().split(" ")[0]);
        String A = br.readLine();
        for (int i = 1; i <= n; i++) {
            a[i] = A.toCharArray()[i-1];
        }
        int m = Integer.parseInt(br.readLine().split(" ")[0]);
        String B = br.readLine();
        for (int i = 1; i <= m; i++) {
            b[i] = B.toCharArray()[i-1];
        }
        //        System.out.println(n+"   "+m);
        //初始化
        for (int i = 1; i <= m; i++) f[0][i] = i; //把a的前0个字母变成b的前i个字母，添加i次
        for (int i = 1; i <= n; i++) f[i][0] = i; //把a的前i个字母变成b的前0个字母，删除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] == b[j]) f[i][j] = Math.min(f[i][j],f[i-1][j-1]);
                else f[i][j] = Math.min(f[i-1][j-1]+1,f[i][j]);
            }
        }
        System.out.println(f[n][m]);
    }
}

新鲜事原文

鼠鼠我
3天前

摆

新鲜事原文

鼠鼠我
3天前

不得不说，JAVA在数据多的时候使用BufferedReader读取比Scanner读取快太多了，同一个程序使用两个读取方法速度能差4倍多

题解 AcWing 897. 最长公共子序列（JAVA）

鼠鼠我
3天前

题目描述

blablabla

JAVA 代码


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N = 1010;
    static char[] a = new char[N];
    static char[] b = new char[N];
    static int[][] f = new int[N][N];//所有a[1-i]和b[1-j]的公共子序列的集合的最大值
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s[] = br.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);
        String A = br.readLine();
        String B = br.readLine();
        for (int i = 1; i <= A.length(); i++) {
            a[i] = A.toCharArray()[i-1];
        }
        for (int i = 1; i <=B.length() ; i++) {
            b[i] = B.toCharArray()[i-1];
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                f[i][j] = Math.max(f[i-1][j],f[i][j-1]);//不相等的时候，两个字符一定有一个可以抛弃，可以对f[i-1][j],f[i][j-1]两种状态取max。
                if(a[i] == b[j]) f[i][j] = Math.max( f[i][j] , f[i-1][j-1]+1);//如果相同 f[i][j] = f[i - 1][j - 1] + 1
            }
        }
        System.out.println(f[n][m]);
    }
}

题解 AcWing 896. 最长上升子序列 II

鼠鼠我
4天前

题目描述

blablabla

JAVA 代码


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    //进来一个数q[i]时，通过二分在f[]中找到最大的小于q[i]的数，就能够将qi接到该数的后面，即更新f[r + 1] = q[i]
    static int N = 100010;
    static int q[] = new int[N];
    static int f[] = new int[N];//所有不同长度上升子序列的结尾的最小值
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String s[] = br.readLine().split(" ");
        for (int i = 1; i <= n; i++) {
            q[i] = Integer.parseInt(s[i-1]);
        }
        int len = 0;//当前的最大长度，也就是f[]里面的最大个数,初始是0
        f[1] = (int) -2e9;//

        for (int i = 1; i <= n; i++) {
            int l =0;int r = len;
            while (l < r){ //二分 找小于某个数的最大的数
                int mid = l+r+1 >> 1;
                if(f[mid] < q[i]) l = mid;//f[] 是找找小于q[i]的最大的数,如果f[mid] < q[i]，说明还没找到距离q[i]的最近的最大的数，继续向右找
                else r = mid-1;
            }
            len = Math.max(len , r+1); // r找的是可以接在哪个数的后面，也就是目前哪个数的比它小的数里面的最大值，找到以后加1
            f[r + 1] = q[i];//r+1长度的上升子序列 的 结尾的最小值 是 q[i]
        }
        System.out.println(len);
    }
}

题解 AcWing 898. 数字三角形

鼠鼠我
5天前

题目描述

blablabla

JAVA 代码



import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{
    static int INF = 0x3f3f3f3f;
    static int N = 510;
    static int p[][] = new int[N][N];
    static int f[][] = new int[N][N];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        for(int i=0;i<=n;i++)
        {
            for(int j=0;j<=n;j++)
            {
                f[i][j] = -INF;
            }
        }
        f[1][1] = p[1][1] = Integer.parseInt(br.readLine());
        for (int i = 2; i <= n; i++) {
            String s[] = br.readLine().split(" ");
            for (int j = 1; j <= i; j++) {
                p[i][j] = Integer.parseInt(s[j-1]);
                f[i][j] = Math.max(f[i-1][j-1],f[i-1][j])+p[i][j];
            }
        }
        int res = -INF;
        for (int i = 1; i <= n; i++) {
            res = Math.max(res,f[n][i]);
        }
        System.out.println(res);

    }
}

题解 AcWing 9. 分组背包问题(JAVA)

鼠鼠我
5天前

题目描述

blablabla

JAVA 代码


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N = 110;
    static int[][] v = new int[N][N];
    static int[][] w = new int[N][N];
    static int[] s = new int[N];
    static int[][] f = new int[N][N];//只从前i组选，且总体积不大于j的所有选法
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s1[] = br.readLine().split(" ");
        int n = Integer.parseInt(s1[0]);
        int V = Integer.parseInt(s1[1]);
        for (int i = 1; i <= n; i++) {
            s[i] = Integer.parseInt(br.readLine());
            for (int j = 1; j <= s[i]; j++) {
                String s2[] = br.readLine().split(" ");
                v[i][j] = Integer.parseInt(s2[0]);
                w[i][j] = Integer.parseInt(s2[1]);
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= V; j++) {
                //不选第i组物品
                f[i][j] = f[i-1][j];
                for (int k = 1; k <= s[i]; k++) {//第i组物品有几个物品
                    //选第i组物品，选哪个
                    if(j >= v[i][k]) f[i][j] = Math.max(f[i][j],f[i-1][j-v[i][k]] + w[i][k]);
                }
            }
        }
        System.out.println(f[n][V]);
    }
}

题解 AcWing 5. 多重背包问题 II（JAVA）

鼠鼠我
6天前

题目描述

blablabla

JAVA代码



import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    /**
     * 1.为什么不能用完全背包问题的思路去解决
     * 因为完全背包没有物品个数限制，所以只要体积够用就可以一直选，没有最后一项。
     * 完全背包最后那一项体积是刚好用完了的，而多重背包最后那一项之后还有体积没用完，所以多重背包的式子后面还可以多减一项，而完全背包就不行了。
     * 2.优化方法及代码
     *
     *
     * 3.01背包问题的优化写法
     * https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-2.html#%E4%B8%80%E7%BB%B4dp%E6%95%B0%E7%BB%84-%E6%BB%9A%E5%8A%A8%E6%95%B0%E7%BB%84
     * @param args
     */
    static int N = 12010;
    static int M = 2010;
    static int v[] = new int[N];
    static int w[] = new int[N];//
    static int f[] = new int[M];//体积小于M
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s1[] = br.readLine().split(" ");
        int n = Integer.parseInt(s1[0]);//物品种数
        int m = Integer.parseInt(s1[1]);//背包容积。
        int cnt = 0;//分组的组别
        for (int i = 1; i <= n; i++) {
            String ss[] = br.readLine().split(" ");
            int a = Integer.parseInt(ss[0]);
            int b = Integer.parseInt(ss[1]);
            int s = Integer.parseInt(ss[2]);
            int k = 1;//组别里面的个数
            /**
             * 第一个组1
             * 第二个组2
             * 第三个组4
             * 第四个组8
             * ...
             */
            while (k <= s){
                cnt++;//组别数先增加
                v[cnt] = a*k;//这个组的整体体积
                w[cnt] = b*k;//这个组的整体价值
                s -= k;//s减小
                k *= 2;//组别数成倍增加
            }
            //剩余的最后一组
            if(s>0){
                cnt++;
                v[cnt] = a*s;
                w[cnt] = b*s;
            }
        }

        n = cnt;//我们每次要枚举的是组数
        //优化后的01背包
        for (int i = 1; i <= n; i++) {
            for (int j = m; j >= v[i]; j--) {
                f[j] = Math.max(f[j],f[j-v[i]]+w[i]);
            }
        }
        System.out.println(f[m]);
    }
}

题目描述

JAVA 代码

0 评论

题目描述

JAVA 代码

0 评论

题目描述

JAVA代码

0 评论

0 评论

0 评论

题目描述

JAVA 代码

0 评论

题目描述

JAVA 代码

0 评论

题目描述

JAVA 代码

0 评论

题目描述

JAVA 代码

0 评论

题目描述

JAVA代码

0 评论